Distance Independent Domination in Graphs

Let \(n \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(I_n\) of vertices of \(G\) is \(n\)-independent if the distance between every two vertices of \(I_n\) is at least \(n+1\). Furthermore, \(I_n\) is defined to be an \(n\)-independent dominating set of \(G\) if \(I_n\) is an \(n\)-independent set in \(G\) and every vertex in \(V(G) – I_nv is at distance at most \(n\) from some vertex in \(I_n\). The \(n\)-independent domination number, \(i_n(G)\), is the minimum cardinality among all \(n\)-independent dominating sets of \(G\). Hence \(i_n(G) = i(G)\) where \(i(G)\) is the independent domination number of \(G\). We establish the existence of a connected graph \(G\) every spanning tree \(T\) of which is such that \(i_n(T) < i_n(G)\). For \(n \in \{1,2\}\) we show that, for any tree \(T\) and any tree \(T’\) obtained from \(T\) by joining a new vertex to some vertex of \(T\), we have \(i_n(T) \geq i_n(T’)\). However, we show that this is not true for \(n \geq 3\). We show that the decision problem corresponding to the problem of computing \(i_n(G)\) is NP-complete, even when restricted to bipartite graphs. Finally, we obtain a sharp lower bound on \(i_n(G)\) for a graph \(G\).