Signed Total $k$-Independence in Digraphs


Lutz Volkmann




Let $k\geq2$ be an integer. A function $f:V(D)\to \{-1,1\}$ defined on the vertex set $V(D)$ of a digraph $D$ is a signed total $k$-independence function if $\sum_{x\in N^-(v)}f(x)\leq k-1$ for each $v\in V(D)$, where $N^-(v)$ consists of all vertices of $D$ from which arcs go into $v$. The weight of a signed total $k$-independence function f is defined by $w(f)=\sum_{x\in V(D)}f(x)$. The maximum of weights $w(f)$, taken over all signed total $k$-independence functions $f$ on $D$, is the signed total $k$-independence number $\alpha^k_{st}(D)$ of $D$. In this work, we mainly present upper bounds on $\alpha^k{st}(D)$, as for example $\alpha^k{st}(D)\leq n-2\lceil(\Delta^-+1-k)/2\rceil$ and \[ \alpha^k_{st}(D)\leq\frac{\Delta^++2k-\delta^+-2}{\Delta^++\delta^+}\cdot n, \] where $n$ is the order, $\Delta^-$ the maximum indegree and $\Delta^+$ and $\delta^+$ are the maximum and minimum outdegree of the digraph $D$. Some of our results imply well-known properties on the signed total 2-independence number of graphs.