Graphs with Total Domination Number Double of the Matching Number

Abstract

A subset $S$ of vertices of a graph $G$ with no isolated vertex is called a total dominating set of $G$ if each vertex of $G$ has at least one neighbor in the set $S$. The total domination number $\gamma_t(G)$ of a graph $G$ is the minimum value of the size of a total dominating set of $G$. A subset $M$ of the edges of a graph $G$ is called a matching if no two edges of $M$ have a common vertex. The matching number $\nu (G)$ of a graph $G$ is the maximum value of the size of a matching in $G$. It can be observed that $\gamma_t(G)\leq 2\nu(G)$ holds for every graph $G$ with no isolated vertex. This paper studies the graphs satisfying the equality and proves that $\gamma_t(G)= 2\nu(G)$ if and only if every connected component of $G$ is either a triangle or a star.

Keywords

• Domination number
• matching number
• total domination number

References

1. M. A. Henning, Trees with large total domination number, Utilitas Mathematica 60 (2001) 99–106.
2. X. Hou, Y. Lu, X. Xu, A characterization of (γt, 2γ)-block graphs, Utilitas Mathematica 82 (2010) 155–159.
3. S. Bahadır, D. Gözüpek, On a class of graphs with large total domination number, Discrete Mathematics & Theoretical Computer Science 20 (1) (2018) 23 8 pages.
4. E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
5. R. C. Brigham, J. R. Carrington, R. P. Vitray, Connected graphs with maximum total domination number, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000) 81–96.
6. M. A. Henning, L. Kang, E. Shan, A. Yeo, On matching and total domination in graphs, Discrete Mathematics 308 (11) (2008) 2313–2318.
7. M. A. Henning, A. Yeo, Total domination and matching numbers in graphs with all vertices in triangles, Discrete Mathematics 313 (2) (2013) 174–181.
8. M. A. Henning, A. Yeo, Total domination and matching numbers in claw-free graphs, The Electronic Journal of Combinatorics 13 (1) (2006) Article Number R59 28 pages.

9. W. C. Shiu, X. Chen, W. H. Chan, Some results on matching and total domination in graphs, Applicable Analysis and Discrete Mathematics 4 (2) (2010) 241–252.
10. S. Bahadır, On total domination and minimum maximal matchings in graphs, Quaestiones Mathematicae 46 (6) (2023) 1119–1129.
11. Y. Büyükçolak, D. Gözüpek, S. Özkan, Equimatchable bipartite graphs, Discussiones Mathematicae Graph Theory 43 (1) (2023) 77–94.
12. D. Zafer, T. Ekim, Critical equimatchable graphs, Australian Journal of Combinatorics 88 (2) (2024) 171–193.
13. Y. Büyükçolak, S. Özkan, D. Gözüpek, Triangle-free equimatchable graphs, Journal of Graph Theory 99 (3) (2022) 461–484.
14. S. Akbari, A. H. Ghodrati, M. A. Hosseinzadeh, A. Iranmanesh, Equimatchable regular graphs, Journal of Graph Theory 87 (1) (2018) 35–45.
15. A. Frendrup, B. Hartnell, P. D. Vestergaard, A note on equimatchable graphs, Australian Journal of Combinatorics 46 (2010) 185–190.