Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
signed distance-$k$-domination number; signed distance-$k$-dominating function; signed domination number
signed distance-$k$-domination number; signed distance-$k$-dominating function; signed domination number
Summary:
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$.
References:
[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
Search
Partner of
