Relating Pairs of Distance Domination Parameters

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(\mathcal{D}\) of vertices of \(G\) is an \(n\)-dominating set (total \(n\)-dominating) set of \(G\) if every vertex of \(V(G) – \mathcal{D}\) (\(V(G)\), respectively) is within distance \(n\) from some vertex of \(\mathcal{D}\) other than itself. The minimum cardinality among all \(n\)-dominating sets (respectively, total \(n\)-dominating sets) of \(G\) is called the \(n\)-domination number (respectively, total \(n\)-domination number) and is denoted by \(\gamma_n(G)\) (respectively, \(\gamma_n^t(G)\)). A set \(\mathcal{I}\) of vertices of \(G\) is \(n\)-independent if the distance (in \(G\)) between every pair of distinct vertices of \(\mathcal{I}\) is at least \(n+1\). The minimum cardinality among all maximal \(n\)-independent sets of \(G\) is called the \(n\)-independence number of \(G\) and is denoted by \(i_n(G)\). Suppose \(\mathcal{I}_k\) is an \(n\)-independent set of \(k\) vertices of \(G\) for which there exists a vertex \(v\) of \(G\) that is within distance \(n\) from every vertex of \(\mathcal{I}_k\). Then a connected subgraph of minimum size that contains the vertices of \(\mathcal{I}_k \cup \{v\}\) is called an \(n\)-generalized \(K_{1,k}\) in \(G\). It is shown that if \(G\) contains no \(n\)-generalized \(K_{1,3}\), then \(\gamma_n(G) = i_n(G)\). Further, it is shown if \(G\) contains no \(n\)-generalized \(K_{1,{k+1}}\), \(k \geq 2\), then \(i_n(G) \leq (k-1)\gamma_n(G) – (k-2)\). It is shown that if \(G\) is a connected graph with at least \(n + 1\) vertices, then there exists a minimum \(n\)-dominating set \(\mathcal{D}\) of \(G\) such that for each \(d \in \mathcal{D}\), there exists a vertex \(v \in V(G) – \mathcal{D}\) at distance \(n\) from \(d\) and distance at least \(n+1\) from every vertex of \(\mathcal{D} – \{d\}\). Using this result, it is shown if \(G\) is a connected graph on \(p \geq 2n+1\) vertices, then \(\gamma_n(G) \leq p/(n + 1)\) and that \(i_n(G) + n\gamma_n(G) \leq p\). Finally, it is shown that if \(T\) is a tree on \(p \geq 2n + 1\) vertices, then \(i_n(G) + n\gamma_n^t(G) \leq p\).