Bounds on the 2-domination number in cactus graphs

Abstract

A $2$-dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex not in $S$ is dominated at least twice. The minimum cardinality of a $2$-dominating set of $G$ is the $2$-domination number $\gamma_{2}(G)$. We show that if $G$ is a nontrivial connected cactus graph with $k(G)$ even cycles ($k(G)\geq 0$), then $\gamma_{2}(G)\geq\gamma_{t}(G)-k(G)$, and if $G$ is a graph of order n with at most one cycle, then $\gamma_{2}(G)\geqslant(n+\ell-s)/2$ improving Fink and Jacobson's lower bound for trees with $\ell>s$, where $\gamma_{t}(G)$, $\ell$ and $s$ are the total domination number, the number of leaves and support vertices of $G$, respectively. We also show that if $T$ is a tree of order $n\geqslant 3$, then $\gamma_{2}(T)\leqslant\beta(T)+s-1$, where $\beta(T)$ is the independence number of $T$.