On \(2\)-Domination and Independence Domination Numbers of Graphs

Abstract

Let \(G\) be a simple graph, and let \(p\) be a positive integer. A subset \(D \subseteq V(G)\) is a \(p\)-dominating set of the graph \(G\), if every vertex \(v \in V(G) – D\) is adjacent to at least \(p\) vertices in \(D\). The \(p\)-domination number \(\gamma_p(G)\) is the minimum cardinality among the \(p\)-dominating sets of \(G\). A subset \(I \subseteq V(G)\) is an independent dominating set of \(G\) if no two vertices in \(I\) are adjacent and if \(I\) is a dominating set in \(G\). The minimum cardinality of an independent dominating set of \(G\) is called independence domination number \(i(G)\).

In this paper, we show that every block-cactus graph \(G\) satisfies the inequality \(\gamma_2(G) \geq i(G)\) and if \(G\) has a block different from the cycle \(C_3\), then \(\gamma_2(G) \geq i(G) + 1\). In addition, we characterize all block-cactus graphs \(G\) with \(\gamma_2(G) = i(G)\) and all trees \(T\) with \(\gamma_2(T) = i(T) + 1\).