PDF
Discussiones Mathematicae Graph Theory 30(2) (2010)
185-199
DOI: https://doi.org/10.7151/dmgt.1486
ON THE (2,2)-DOMINATION NUMBER OF TREES
You Lu, Xinmin Hou and Jun-Ming Xu
Department of Mathematics
University of Science and Technology of China
Hefei, Anhui, 230026, China
e-mail: xmhou@ustc.edu.cn
Abstract
Let γ(G) and γ2,2(G) denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that [(2(γ(T)+1))/3] ≤ γ2,2(T) ≤ 2γ(T). Moreover, we characterize all the trees achieving the equalities.Keywords: domination number, total domination number, (2,2)-domination number.
2010 Mathematics Subject Classification: 05C69.
References
| [1] | T.J. Bean, M.A. Henning and H.C. Swart, On the integrity of distance domination in graphs, Australas. J. Combin. 10 (1994) 29-43. |
| [2] | G. Chartrant and L. Lesniak, Graphs & Digraphs (third ed., Chapman & Hall, London, 1996). |
| [3] | M. Fischermann and L. Volkmann, A remark on a conjecture for the (k,p)-domination number, Utilitas Math. 67 (2005) 223-227. |
| [4] | M.A. Henning, Trees with large total domination number, Utilitas Math. 60 (2001) 99-106. |
| [5] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (New York, Marcel Deliker, 1998). |
| [6] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (New York, Marcel Deliker, 1998). |
| [7] | T. Korneffel, D. Meierling and L. Volkmann, A remark on the (2,2)-domination number Discuss. Math. Graph Theory 28 (2008) 361-366, doi: 10.7151/dmgt.1411. |
Received 19 September 2008
Revised 4 June 2009
Accepted 4 June 2009
Close