ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 28(1) (2008) 59-66
DOI: 10.7151/dmgt.1391


Xue-Gang Chen

Department of Mathematics
North China Electric Power University
Beijing 102206, China

Wai Chee Shiu

Department of Mathematics
Hong Kong Baptist University
224 Waterloo Road, Kowloon Tong, Hong Kong, China

Hong-Yu Chen

The College of Information Science and Engineering
Shandong University of Science and Technology
Qingdao, Shandong Province 266510, China


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.


[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