zbMATH — the first resource for mathematics

On matching and semitotal domination in graphs. (English) Zbl 1284.05196
Summary: Let \(G\) be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number, \(\gamma (G)\), and the total domination number, \(\gamma_t (G)\). A set \(S\) of vertices in \(G\) is a semitotal dominating set of \(G\) if it is a dominating set of \(G\) and every vertex in \(S\) is within distance 2 of another vertex of \(S\). The semitotal domination number, \(\gamma_{t2}(G)\), is the minimum cardinality of a semitotal dominating set of \(G\). We observe that \(\gamma (G)\leq \gamma_{t2}(G)\leq\gamma_ t(G)\). It is known that \(\gamma (G)\leq\alpha '(G)\), where \(\alpha '(G)\) denotes the matching number of \(G\). However, the total domination number and the matching number of a graph are generally incomparable.
We provide a characterization of minimal semitotal dominating sets in graphs. Using this characterization, we prove that if \(G\) is a connected graph on at least two vertices, then \(\gamma_{t2}(G)\leq\alpha '(G)+1\) and we characterize the graphs achieving equality in the bound.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI
[1] Bollobás, B.; Cockayne, E. J., Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, 241-249, (1979) · Zbl 0418.05049
[2] Cockayne, E. J.; Dawes, R. M.; Hedetniemi, S. T., Total domination in graphs, Networks, 10, 211-219, (1980) · Zbl 0447.05039
[3] Cockayne, E. J.; Hedetniemi, S. T.; Slater, P. J., Matchings and transversals in hypergraphs, domination and independence-in trees, J. Combin. Theory B, 27, 78-80, (1979) · Zbl 0414.05036
[4] DeLaViña, E.; Liu, Q.; Pepper, R.; Waller, B.; West, D. B., Some conjectures of graffiti.pc on total domination, Congr. Numer., 185, 81-95, (2007) · Zbl 1134.05070
[5] Goddard, W.; Henning, M. A.; McPillan, C. A., Semitotal domination in graphs, Util. Math., (2014), (in press) · Zbl 1300.05220
[6] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of domination in graphs, (1998), Marcel Dekker, Inc. New York · Zbl 0890.05002
[7] (Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Domination in Graphs: Advanced Topics, (1998), Marcel Dekker, Inc. New York) · Zbl 0883.00011
[8] Henning, M. A., Recent results on total domination in graphs: a survey, Discrete Math, 309, 32-63, (2009) · Zbl 1219.05121
[9] Henning, M. A.; Kang, L.; Shan, E.; Yeo, A., On matching and total domination in graphs, Discrete Math., 308, 2313-2318, (2008) · Zbl 1145.05042
[10] M.A. Henning, A. Yeo, Total Domination in Graphs, in: Springer Monographs in Mathematics, 2013, ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online). · Zbl 1408.05002
[11] Henning, M. A.; Yeo, A., Total domination and matching numbers in claw-free graphs, Electron. J. Combin., 13, (2006), #59 · Zbl 1100.05071
[12] Henning, M. A.; Yeo, A., Perfect matchings in total domination critical graphs, Graphs Combin., 27, 685-701, (2011) · Zbl 1234.05187
[13] Henning, M. A.; Yeo, A., Total domination and matching numbers in graphs with all vertices in triangles, Discrete Math., 313, 174-181, (2013) · Zbl 1256.05171
[14] Henning, M. A.; Yeo, A., Total domination number versus matching number, (Total Domination in Graphs, Springer Monographs in Mathematics, (2013)), 77-81
[15] Plummer, M., Factors and factorization, (Gross, J. L.; Yellen., J., Handbook of Graph Theory, (2003), CRC Press), 403-430, ISBN: 1-58488-092-2
[16] Pulleyblank, W. R., Matchings and extension, (Graham, R. L.; Grötschel, M.; Lovász., L., Handbook of Combinatorics, (1995), Elsevier Science B.V), 179-232 · Zbl 0866.05048
[17] Shiu, W. C.; Chen, X.; Chan, W. H., Some results on matching and total domination in graphs, Appl. Anal. Discrete Math., 4, 241-252, (2010) · Zbl 1265.05471
[18] Wang, H.; Kang, L.; Shan, E., Matching properties on total domination vertex critical graphs, Graphs Combin., 25, 6, 851-861, (2009) · Zbl 1205.05172
[19] O, S.; West, D. B., Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, J. Graph Theory, 64, 116-131, (2010) · Zbl 1201.05049
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.