TY  - JOUR
ID  - Chellali2006
LB  - Chellali2006
AU  - Chellali, Mustapha
TI  - Bounds on the 2-domination number in cactus graphs
ST  - Bounds on the 2-domination number in cactus graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2006
VL  - 26
IS  - 1
SP  - 5
EP  - 12
DO  - http://dx.doi.org/10.7494/OpMath.2006.26.1.5
UR  - http://dx.doi.org/10.7494/OpMath.2006.26.1.5
AB  - 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\).
KW  - 2-domination number
KW  - total domination number
KW  - independence number
KW  - cactus graphs
KW  - trees
SN  - 1232-9274
ER  -