Total domination versus triad domination

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 Department of Mathematics and Statistics, East Tennessee State University, Johnson City, TN 37614-0002 USA

2 Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006 South Africa

Abstract

A dominating set in a graph $G$ is a set $S$ of vertices of $G$ such that every vertex in $V(G) \setminus S$ is adjacent to a vertex in $S$. A total dominating set in $G$ is a dominating set $S$ with the additional property that the subgraph $G[S]$ induced by $S$ is isolate-free. A triad dominating set $S$ (also called a $3$-component dominating set in the literature) is a dominating set in which every component in $G[S]$ has order at least~$3$. The triad domination number, denoted $\gamma_{td}(G)$, of $G$ is the minimum cardinality among all triad dominating sets of $G$. We observe that $\gamma(G) \le \gamma_t(G) \le \gamma_{td}(G)$, where $\gamma(G)$ is the domination number of $G$ and $\gamma_t(G)$ is the total domination number of $G$. We show that the ratio $\frac{\gamma_{td}(G)}{\gamma_t(G)}$ is at most $\frac{3}{2}$. We establish properties of the graphs $G$ satisfying $\gamma_{td}(G) = \frac{3}{2}\gamma_t(G)$ and characterize the trees achieving this equality.

Keywords

Main Subjects

References

[1] J.D. Alvarado, S. Dantas, and D. Rautenbach, Dominating sets inducing large components, Discrete Math. 339 (2016), no. 11, 2715–2720. https://doi.org/10.1016/j.disc.2016.05.016
[2] , Dominating sets inducing large components in maximal outerplanar graphs, J. Graph Theory 88 (2018), no. 2, 356–370. https://doi.org/10.1002/jgt.22217
[3] D. Favaron, O. and. Kratsch, Ratios of domination parameters, Advances in Graph Theory, Vishwa International Publications, 1991, pp. 173–182.
[4] Z. Gao, R. Lang, C. Xi, and J. Yue, 3-component domination numbers in graphs, Discrete Math. 347 (2024), no. 4, 113859. https://doi.org/10.1016/j.disc.2023.113859
[5] Z. Gao, R. Lang, C. Xi, and J. Yue, On 3-component domination numbers in graphs, Discrete Appl. Math. 366 (2025), 53–62. https://doi.org/10.1016/j.dam.2025.01.016
[6] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, vol. 64, Springer Cham, 2020.
[7] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Structures of Domination in Graphs, vol. 66, Springer Cham, 2021.
[8] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts, Springer Cham, 2023.

[9] T.W. Haynes and M.A. Henning, Connected domination versus dominating sets inducing large components, Discrete Math. In press.
[10] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer New York, NY, 2013.
[11] W. Yang and B. Wu, Dominating sets inducing large component in graphs with minimum degree two, Graphs Combin. 39 (2023), no. 5, Article number: 99. https://doi.org/10.1007/s00373-023-02687-z
[12] W. Yang and B. Wu, Proof of a conjecture on dominating sets inducing large component in graphs with minimum degree two, Discrete Math. 347 (2024), no. 10, 114122.  https://doi.org/10.1016/j.disc.2024.114122
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 07 November 2025

Files

Share

How to cite

Statistics