Trees with equal total domination and total restrained domination numbers

• Autorzy: Xue-Gang Chen , Wai Chee Shiu , Hong-Yu Chen
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

total domination number; total restrained domination number; tree

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2008
• Tom: 28
• Numer: 1
• Strony: 59-66

Daty

wydano

2008

otrzymano

2006-09-22

poprawiono

2007-01-24

zaakceptowano

2007-01-24

Twórcy

autor

Xue-Gang Chen

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

autor

Wai Chee Shiu

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

autor

Hong-Yu Chen

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

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1391