@Article{Chellali2006,
author = "Chellali, Mustapha",
title = "Bounds on the 2-domination number in cactus graphs",
journal = "Opuscula Math.",
year = "2006",
volume = "26",
number = "1",
pages = "5--12",
doi = "http://dx.doi.org/10.7494/OpMath.2006.26.1.5",
url = "http://dx.doi.org/10.7494/OpMath.2006.26.1.5",
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",
issn = "1232-9274"
}