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)