Discussiones Mathematicae Graph Theory 28(1) (2008)
59-66
DOI: https://doi.org/10.7151/dmgt.1391
TREES WITH EQUAL TOTAL DOMINATION AND TOTAL RESTRAINED DOMINATION NUMBERS
Xue-Gang Chen
Department of Mathematics | Wai Chee Shiu
Department of Mathematics | Hong-Yu Chen
The College of Information Science and Engineering |
Abstract
For a graph G = (V,E), a set S ⊆ V(G) is a total dominating set if it is dominating and both 〈S〉 has no isolated vertices. The cardinality of a minimum total dominating set in G is the total domination number. A set S ⊆ V(G) is a total restrained dominating set if it is total dominating and 〈 V(G)−S〉 has no isolated vertices. The cardinality of a minimum total restrained dominating set in G is the total restrained domination number. We characterize all trees for which total domination and total restrained domination numbers are the same.Keywords: total domination number, total restrained domination number, tree.
2000 Mathematics Subject Classification: 05C69.
References
[1] | S. Arumugam and J. Paulraj Joseph, On graphs with equal domination and connected domination numbers, Discrete Math. 206 (1999) 45-49, doi: 10.1016/S0012-365X(98)00390-2. |
[2] | G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar and L.R. Marcus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69, doi: 10.1016/S0012-365X(99)00016-3. |
[3] | F. Harary and M. Livingston, Characterization of tree with equal domination and independent domination numbers, Congr. Numer. 55 (1986) 121-150. |
[4] | D. Ma, X. Chen and L. Sun, On total restrained domination in graphs, Czechoslovak Math. J. 55 (2005) 165-173, doi: 10.1007/s10587-005-0012-2. |
[5] | G.S. Domke, J.H. Hattingh, S.T. Hedetniemi and L.R. Markus, Restrained domination in trees, Discrete Math. 211 (2000) 1-9, doi: 10.1016/S0012-365X(99)00036-9. |
[6] | E.J. Cockayne, C.M. Mynhardt and B. Yu, Total dominating functions in trees: minimality and convexity, J. Graph Theory 19 (1995) 83-92, doi: 10.1002/jgt.3190190109. |
Received 22 September 2006
Revised 24 January 2007
Accepted 24 January 2007
Close