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