$(r,s)$-Domination in Graphs and Directed Graphs

Abstract

Let $G=(V,E)$ be a graph or digraph, and let $r$ and $s$ be two positive integers. A subset $U$ of $V$ is called an $(r,s)$ dominating set if for any $v\in V–U$, there exists $u\in U$ such that $d(u,v)\le r$ and for any $u\in U$ there exists $u^{\prime }\in U$ ($u^{\prime }\ne u$) for which $d(u^{\prime },u)\le s$. For graphs, a $(1,1)$-dominating set is the same as a total dominating set. The $(r,s)$-domination number ${\delta }_{r,s}(G)$ of a graph or digraph $G$ is the cardinality of a smallest $(r,s)$-dominating set of $G$. Various bounds on ${\delta }_{r,s}(G)$ are established including that, for an arbitrary connected graph of order $n\ge 2$, if $s\le r+1$ then ${\delta }_{r,s}(G)\le max(\frac{2n}{r+s+1},2)$, and if $s\ge r+1$ then ${\delta }_{r,s}(G)<max(\frac{n}{r+1},2)$. Both bounds are sharp.