Some Extremal Results on Independent Distance Domination in Graphs

Let \(s\) and \(r\) be positive integers with \(s \geq r\) and let \(G\) be a graph. A set \(I\) of vertices of \(G\) is an \((r, s)\)-set if no two vertices of \(I\) are within distance \(r\) from each other and every vertex of \(G\) not in \(I\) is within distance \(s\) from some vertex of \(I\). The minimum cardinality of an \((r, s)\)-set is called the \((r, s)\)-domination number and is denoted by \(i_{r,s}(G)\). It is shown that if \(G\) is a connected graph with at least \(s > r \geq 1\) vertices, then there is a minimum \((r,s)\)-set \(I\) of \(G\) such that for each \(v \in I\), there exists a vertex \(w \in V(G) – I\) at distance at least \(s-r\) from \(v\), but within distance \(s\) from \(v\), and at distance greater than \(s\) from every vertex of \(I – \{v\}\). Using this result, it is shown that if \(G\) is a connected graph with \(p \geq 9 \geq 2\) vertices, then \(i_{r,s}(G) < p/s\) and this bound is best possible. Further, it is shown that for \(s \in \{1,2,3\}\), if \(T\) is a tree on \(p \geq s +1\) vertices, then \(i_{r,s}(T) \leq p/(s +1)\) and this bound is sharp.