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)\ge i(G)$ and if $G$ has a block different from the cycle $C_3$, then ${\gamma }_2(G)\ge 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$.