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
Close