Signed total $k$-independence in digraphs

Lutz Volkmann


Let $k\ge 2$ be an integer. A function $f:V(D)\rightarrow\{-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)\le 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_{st}^k(D)$ of $D$.

In this work, we mainly present upper bounds on $\alpha_{st}^k(D)$, as for example
$\alpha_{st}^k(D)\le n-2\lceil(\Delta^-+1-k)/2\rceil$ and
$$\alpha_{st}^k(D)\le\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.

Full Text:



  • There are currently no refbacks.