An algorithm to find two distance domination parameters in a graph (Q1917347)

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called total \(n\)-dominating, if for each \(x \in V(G)\) there exists a vertex \(y \in D\) distinct from \(x\) such that the distance between \(x\) and \(y\) is less than or equal to \(n\). A subset \(S\) of \(V(G)\) is called \(n\)-independent, if the distance between any two vertices of \(S\) is at least \(n + 1\). The minimum number of vertices of a total \(n\)-dominating set in \(G\) is the total \(n\)-domination number \(\gamma_n' (G)\), the minimum number of vertices of a maximal (with respect to set inclusion) \(n\)-independent set in \(G\) is the \(n\)-independence number \(i_n (G)\) of \(G\). The paper presents an algorithm for finding a total \(n\)-dominating set and a maximal \(n\)-independent set in a graph \(G\) with \(p \geq 2n + 1\) vertices. For such graphs the inequality \(i_n (G) + n \gamma_n' (G) \leq p\) is proved.