Lower bounds for the domination number

Ermelinda Delaviña; Ryan Pepper; Bill Waller

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 3, page 475-487
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Ermelinda Delaviña, Ryan Pepper, and Bill Waller. "Lower bounds for the domination number." Discussiones Mathematicae Graph Theory 30.3 (2010): 475-487. <http://eudml.org/doc/270791>.

@article{ErmelindaDelaviña2010,
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.},
author = {Ermelinda Delaviña, Ryan Pepper, Bill Waller},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; radius; matching; cut-vertices},
language = {eng},
number = {3},
pages = {475-487},
title = {Lower bounds for the domination number},
url = {http://eudml.org/doc/270791},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Ermelinda Delaviña
AU - Ryan Pepper
AU - Bill Waller
TI - Lower bounds for the domination number
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 3
SP - 475
EP - 487
AB - 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.
LA - eng
KW - domination number; radius; matching; cut-vertices
UR - http://eudml.org/doc/270791
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing, 1976). Zbl1226.05083
  2. [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, 1990). Zbl0688.05017
  3. [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. Zbl1114.05071
  4. [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. Zbl0644.05029
  5. [5] E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. Zbl0447.05039
  6. [6] P. Dankelmann, Average distance and the independence number, Discrete Appl. Math. 51 (1994) 73-83, doi: 10.1016/0166-218X(94)90095-7. Zbl0803.05020
  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. Zbl0888.05024
  8. [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. Zbl1134.05070
  9. [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. Zbl1211.05105
  10. [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. Zbl0982.05044
  11. [11] P. Erdös, M. Saks and V. Sós, Maximum Induced Tress in Graphs, J. Graph Theory 41 (1986) 61-79. 
  12. [12] S. Fajtlowicz and W. Waller, On two conjectures of Graffiti, Congr. Numer. 55 (1986) 51-56. Zbl0639.05040
  13. [13] S. Fajtlowicz, Written on the Wall (manuscript), Web address: http://math.uh.edu/siemion. 
  14. [14] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409. Zbl0713.05037
  15. [15] O. Favaron, M. Maheo and J-F. Sacle, Some Results on Conjectures of Graffiti - 1, Ars Combin. 29 (1990) 90-106. Zbl0743.05061
  16. [16] M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Co. (New York, Bell Telephone Lab., 1979). 
  17. [17] P. Hansen, A. Hertz, R. Kilani, O. Marcotte and D. Schindl, Average distance and maximum induced forest, pre-print, 2007. Zbl1182.05049
  18. [18] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998). Zbl0890.05002
  19. [19] T. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, Inc., NY, 1998). Zbl0883.00011
  20. [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. Zbl1063.05035
  21. [21] L. Lovász and M.D. Plummer, Matching Theory (Acedemic Press, New York, 1986). 
  22. [22] D.B. West, Open problems column #23, SIAM Activity Group Newsletter in Discrete Mathematics, 1996. 
  23. [23] D.B. West, Introduction to Graph Theory (2nd ed.) (Prentice-Hall, NJ, 2001). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.