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

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) \leq r\) and for any \(u \in U\) there exists \(u’ \in U\) (\(u’ \neq u\)) for which \(d(u’,u) \leq 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 \geq 2\), if \(s \leq r+1\) then \(\delta_{r,s}(G) \leq \max\left(\frac{2n}{r+s+1},2\right)\), and if \(s \geq r+1\) then \(\delta_{r,s}(G) < \max\left(\frac{n}{r+1},2\right)\). Both bounds are sharp.