Download PDF - Lower bounds for the domination numberAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Lower bounds for the domination number

Authors 1, 1, 1

Affiliations

  1. 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

ENG
domination number, radius, matching, cut-vertices

Bibliography

  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).
Discussiones Mathematicae Graph Theory
2010/30/3
Export to PBN, Opens in new tab
Pages:
475-487
Main language of publication
English
Received
2008-04-18
Accepted
2009-04-29
Published
2010

DOI: 10.7151/dmgt.1508

Exact and natural sciences