Graphs with Total Domination Number Double of the Matching Number

Year 2024, Issue: 49, 1 - 6, 31.12.2024

Selim Bahadır

https://doi.org/10.53570/jnt.1520557

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

• M. A. Henning, Trees with large total domination number, Utilitas Mathematica 60 (2001) 99–106.
• X. Hou, Y. Lu, X. Xu, A characterization of (γt, 2γ)-block graphs, Utilitas Mathematica 82 (2010) 155–159.
• 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.
• E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211–219.
• 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.
• M. A. Henning, L. Kang, E. Shan, A. Yeo, On matching and total domination in graphs, Discrete Mathematics 308 (11) (2008) 2313–2318.
• M. A. Henning, A. Yeo, Total domination and matching numbers in graphs with all vertices in triangles, Discrete Mathematics 313 (2) (2013) 174–181.
• 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.
• 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.
• S. Bahadır, On total domination and minimum maximal matchings in graphs, Quaestiones Mathematicae 46 (6) (2023) 1119–1129.
• Y. Büyükçolak, D. Gözüpek, S. Özkan, Equimatchable bipartite graphs, Discussiones Mathematicae Graph Theory 43 (1) (2023) 77–94.
• D. Zafer, T. Ekim, Critical equimatchable graphs, Australian Journal of Combinatorics 88 (2) (2024) 171–193.
• Y. Büyükçolak, S. Özkan, D. Gözüpek, Triangle-free equimatchable graphs, Journal of Graph Theory 99 (3) (2022) 461–484.
• S. Akbari, A. H. Ghodrati, M. A. Hosseinzadeh, A. Iranmanesh, Equimatchable regular graphs, Journal of Graph Theory 87 (1) (2018) 35–45.
• A. Frendrup, B. Hartnell, P. D. Vestergaard, A note on equimatchable graphs, Australian Journal of Combinatorics 46 (2010) 185–190.