×

A classification of cactus graphs according to their total domination number. (English) Zbl 1434.05110

Summary: A set \(S\) of vertices in a graph \(G\) is a total dominating set of \(G\) if every vertex in \(G\) is adjacent to some vertex in \(S\). The total domination number, \(\gamma_t(G)\), is the minimum cardinality of a total dominating set of \(G\). A cactus is a connected graph in which every edge belongs to at most one cycle. Equivalently, a cactus is a connected graph in which every block is an edge or a cycle. Let \(G\) be a connected graph of order \(n \ge 2\) with \(k \ge 0\) cycles and \(\ell\) leaves. Recently, the authors [“A new lower bound on the total domination number of a graph”, manuscript] have proved that \(\gamma_t(G) \ge \frac{1}{2}(n-\ell + 2) - k\). As a consequence of this bound, \(\gamma_t(G) = \frac{1}{2}(n-\ell + 2 + m) - k\) for some integer \(m \ge 0\). In this paper, we characterize the class of cactus graphs achieving equality in this bound, thereby providing a classification of all cactus graphs according to their total domination number.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Software:

Graffiti.pc
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chellali, M.; Haynes, Tw, A note on the total domination number of a tree, J. Comb. Math. Comb. Comput., 58, 189-193 (2006) · Zbl 1114.05071
[2] Cockayne, Ej; Henning, Ma; Mynhardt, Cm, Vertices contained in all or in no minimum total dominating set of a tree, Discrete Math., 260, 37-44 (2003) · Zbl 1013.05054 · doi:10.1016/S0012-365X(02)00447-8
[3] Desormeaux, Wj; Henning, Ma, Lower bounds on the total domination number of a graph, J. Comb. Optim., 31, 1, 52-66 (2016) · Zbl 1331.05168 · doi:10.1007/s10878-014-9708-2
[4] Hajian, M., Henning, M.A., Jafari Rad, N.: A new lower bound on the total domination number of a graph (manuscript) · Zbl 1440.05160
[5] Henning, Ma, Essential upper bounds on the total domination number, Discrete Appl. Math., 244, 103-115 (2018) · Zbl 1387.05183 · doi:10.1016/j.dam.2018.03.008
[6] Henning, Michael A.; Yeo, Anders, Total Domination Critical Graphs, Springer Monographs in Mathematics, 83-101 (2013), New York, NY: Springer New York, New York, NY · Zbl 1408.05002
[7] Henning, M.A., Yeo, A.: Total Domination in Trees. Chapter 3 in [7], pp. 19-29
[8] Henning, Michael A.; Yeo, Anders, Total Domination and Minimum Degree, Springer Monographs in Mathematics, 39-54 (2013), New York, NY: Springer New York, New York, NY · Zbl 1408.05002
[9] Henning, Ma; Yeo, A., A new lower bound for the total domination number in graphs proving a Graffiti conjecture, Discrete Appl. Math., 173, 45-52 (2014) · Zbl 1297.05179 · doi:10.1016/j.dam.2014.03.013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.