Previous |  Up |  Next


signed distance-$k$-domination number; signed distance-$k$-dominating function; signed domination number
The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k(v)$, is the set $N_k(v)=\lbrace u\mid u\ne v$ and $d(u,v)\le k\rbrace $. $N_k[v]=N_k(v)\cup \lbrace v\rbrace $ is the closed $k$-neighborhood of $v$. A function $f\: V\rightarrow \lbrace -1,1\rbrace $ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f(N_k[v])=\sum _{u\in N_k[v]}f(u)\ge 1$. The signed distance-$k$-domination number, denoted by $\gamma _{k,s}(G)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of $\gamma _{2,s}(G)$ are found for graphs with small diameter, paths, circuits. At the end it is proved that $\gamma _{2,s}(T)$ is not bounded from below in general for any tree $T$.
[1] J. H.  Hattingh, M. A.  Henning, and E.  Ungerer: Partial signed domination in graphs. Ars Combin. 48 (1998), 33–42. MR 1623038
[2] T. W.  Haynes, S. T.  Hedetniemi, and P. J.  Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. MR 1605684
[3] T. W.  Haynes, S. T.  Hedetniemi, and P. J.  Slater: Domination in Graphs: Advanced Topics. Marcel Dekker, New York, 1998. MR 1605685
[4] M. A.  Henning: Domination in regular graphs. Ars Combin. 43 (1996), 263–271. MR 1415996 | Zbl 0881.05101
Partner of
EuDML logo