PDF

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

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