On signed distance-$k$-domination in graphs

Xing, Huaming ; Sun, Liang ; Chen, Xuegang

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 1, pp. 229-238.

Résumé

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$.

Détail

Classification : 05C69
Mots-clés : signed distance-$k$-domination number; signed distance-$k$-dominating function; signed domination number