Discussiones Mathematicae Graph Theory 30(3) (2010) 475-487
doi: 10.7151/dmgt.1508

[BIBTex] [PDF] [PS]

LOWER BOUNDS FOR THE DOMINATION NUMBER

Ermelinda Delaviña,  Ryan Pepper and  Bill Waller

University of Houston - Downtown
Houston, TX, 77002, USA

Abstract

In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.

Keywords: domination number, radius, matching, cut-vertices.

2010 Mathematics Subject Classification: 05C69 (05C12, 05C70).

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing, 1976).
[2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, 1990).
[3] M. Chellali and T. Haynes, A Note on the Total Domination Number of a Tree, J. Combin. Math. Combin. Comput. 58 (2006) 189-193.
[4] F. Chung, The average distance is not more than the independence number, J. Graph Theory 12 (1988) 229-235, doi: 10.1002/jgt.3190120213.
[5] E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304.
[6] P. Dankelmann, Average distance and the independence number, Discrete Appl. Math. 51 (1994) 73-83, doi: 10.1016/0166-218X(94)90095-7.
[7] P. Dankelmann, Average distance and the domination number, Discrete Appl. Math. 80 (1997) 21-35, doi: 10.1016/S0166-218X(97)00067-X.
[8] E. DeLaViña, Q. Liu, R. Pepper, W. Waller and D.B. West, Some Conjectures of Graffiti.pc on Total Domination, Congr. Numer. 185 (2007) 81-95.
[9] E. DeLaViña, R. Pepper and W. Waller, A Note on Dominating Sets and Average Distance, Discrete Math. 309 (2009) 2615-2619, doi: 10.1016/j.disc.2008.03.018.
[10] A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Applicandae Mathematicae 66 (2001) 211-249, doi: 10.1023/A:1010767517079.
[11] P. Erdös, M. Saks and V. Sós, Maximum Induced Tress in Graphs, J. Graph Theory 41 (1986) 61-79.
[12] S. Fajtlowicz and W. Waller, On two conjectures of Graffiti, Congr. Numer. 55 (1986) 51-56.
[13] S. Fajtlowicz, Written on the Wall (manuscript), Web address: http://math.uh.edu/~siemion.
[14] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409.
[15] O. Favaron, M. Maheo and J-F. Sacle, Some Results on Conjectures of Graffiti - 1, Ars Combin. 29 (1990) 90-106.
[16] M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Co. (New York, Bell Telephone Lab., 1979).
[17] P. Hansen, A. Hertz, R. Kilani, O. Marcotte and D. Schindl, Average distance and maximum induced forest, pre-print, 2007.
[18] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998).
[19] T. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, Inc., NY, 1998).
[20] M. Lemańska, Lower Bound on the Domination Number of a Tree, Discuss. Math. Graph Theory 24 (2004) 165-170, doi: 10.7151/dmgt.1222.
[21] L. Lovász and M.D. Plummer, Matching Theory (Acedemic Press, New York, 1986).
[22] D.B. West, Open problems column #23, SIAM Activity Group Newsletter in Discrete Mathematics, 1996.
[23] D.B. West, Introduction to Graph Theory (2nd ed.) (Prentice-Hall, NJ, 2001).

Received 18 April 2008
Revised 29 April 2009
Accepted 20 October 2009