PDF
Discussiones Mathematicae Graph Theory 30(3) (2010)
425-435
DOI: https://doi.org/10.7151/dmgt.1504
A CHARACTERIZATION OF (γt,γ2)-TREES
You Lu, Xinmin Hou, Jun-Ming Xu and Ning Li
Department of Mathematics
University of Science and Technology of China
Hefei, Anhui, 230026, China
e-mail: xmhou@ustc.edu.cn
Abstract
Let γt(G) and γ2(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γt(T) ≤ γ2(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.Keywords: domination, total domination, 2-domination, (λ,μ)-tree.
2010 Mathematics Subject Classification: 05C69.
References
[1] | M. Blidia, M. Chellalia and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, Discrete Math. 306 (2006) 1840-1845, doi: 10.1016/j.disc.2006.03.061. |
[2] | M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domination number in trees, Discrete Math. 306 (2006) 2031-2037, doi: 10.1016/j.disc.2006.04.010. |
[3] | E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. |
[4] | E.J. Cockayne, O. Favaron, C.M. Mynhardt and J. Puech, A characterization of (γ,i)-trees, J. Graph Theory 34 (2000) 277-292, doi: 10.1002/1097-0118(200008)34:4<277::AID-JGT4>3.0.CO;2-#. |
[5] | G. Chartrant and L. Lesniak, Graphs & Digraphs, third ed. (Chapman & Hall, London, 1996). |
[6] | J.F. Fink and M.S. Jacobson, n-Domination in graphs, in: Y. Alavi, A.J. Schwenk (eds.), Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 283-300. |
[7] | F. Harary and M. Livingston, Characterization of trees with equal domination and independent domination numbers, Congr. Numer. 55 (1986) 121-150. |
[8] | T.W. Haynes, S.T. Hedetniemi, M.A. Henning and P.J. Slater, H-forming sets in graphs, Discrete Math. 262 (2003) 159-169, doi: 10.1016/S0012-365X(02)00496-X. |
[9] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (New York, Marcel Deliker, 1998). |
[10] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (New York, Marcel Deliker, 1998). |
[11] | T.W. Haynes, M.A. Henning and P.J. Slater, Strong quality of domination parameters in trees, Discrete Math. 260 (2003) 77-87, doi: 10.1016/S0012-365X(02)00451-X. |
[12] | M.A. Henning, A survey of selected recently results on total domination in graphs, Discrete Math. 309 (2009) 32-63, doi: 10.1016/j.disc.2007.12.044. |
[13] | X. Hou, A characterization of (2γ, γp)-trees, Discrete Math. 308 (2008) 3420-3426, doi: 10.1016/j.disc.2007.06.034. |
Received 27 February 2009
Revised 28 July 2009
Accepted 1 September 2009
Close