Opuscula Math. 26, no. 1 (2006), 5-12

Opuscula Mathematica

# Bounds on the 2-domination number in cactus graphs

Mustapha Chellali

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$$.

Keywords: 2-domination number, total domination number, independence number, cactus graphs, trees.

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Mustapha Chellali
• University of Blida, Department of Mathematics, B.P. 270, Blida, Algeria