Article in volume
Authors:
Nader Jafari Rad
Department of Mathematics Shahrood Niversity of TechnologyUniversity Blvd. Shahrood IRAN
email: n.jafarirad@gmail.com
Title:
A classification of cactus graphs according to their domination number
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 613-626
Received: 2019-10-10 , Revised: 2020-01-03 , Accepted: 2020-01-03 , Available online: 2020-01-27 , https://doi.org/10.7151/dmgt.2295
Abstract:
A set $S$ of vertices in a graph $G$ is a dominating set of $G$ if every vertex
not in $S$ is adjacent to some vertex in $S$. The domination number, $\gamma(G)$,
of $G$ is the minimum cardinality of a dominating set of $G$. The authors
proved
in [A new lower bound on the domination number of a graph, J. Comb. Optim.
38 (2019) 721–738] that if $G$ is a connected graph of order $n \ge 2$ with
$k \ge 0$ cycles and $\ell$ leaves, then $\gamma(G) \ge \lceil (n-\ell+2 - 2k)/3
\rceil$. As a consequence of the above bound, $\gamma(G) = (n-\ell+2(1-k)+m)/3$
for some integer $m \ge 0$. In this paper, we characterize the class of cactus
graphs achieving equality here, thereby providing a classification of all cactus
graphs according to their domination number.
Keywords:
domination number, lower bounds, cycles, cactus graphs
References:
- Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62–71.
https://doi.org/10.1016/j.ejc.2011.08.002 - E. DeLaViña, R. Pepper and W. Waller, A note on dominating sets and average distance, Discrete Math. 309 (2009) 2615–2619.
https://doi.org/10.1016/j.disc.2008.03.018 - E. DeLaViña, R. Pepper and W. Waller, Lower bounds for the domination number, Discuss. Math. Graph Theory 30 (2010) 475–487.
https://doi.org/10.7151/dmgt.1508 - R. Gera, T.W. Haynes, S.T. Hedetniemi and M.A. Henning, An annotated glossary of graph theory parameters, with conjectures, in: Graph Theory –- Favorite Conjectures and Open Problems. 2, R. Gera. T.W. Haynes and S.T. Hedetniemi (Ed(s)), (Springer, Switzerland 2018) 177–281.
- M. Hajian, M.A. Henning and N. Jafari Rad, A new lower bound on the domination number of a graph, J. Comb. Optim. 38 (2019) 721–738.
https://doi.org/10.1007/s10878-019-00409-x - T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
- T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
- M.A. Henning and A. Yeo, Total Domination in Graphs (Springer Monographs in Mathematics, 2013).
https://doi.org/10.1007/978-1-4614-6525-6 - M. Lemańska, Lower bound on the domination number of a tree, Discuss. Math. Graph Theory 24 (2004) 165–169.
https://doi.org/10.7151/dmgt.1222
Close