Lower bounds for the domination number
Ermelinda Delaviña ; Ryan Pepper ; Bill Waller
Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 475-487 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:270791 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1508,
     author = {Ermelinda Delavi\~na and Ryan Pepper and Bill Waller},
     title = {Lower bounds for the domination number},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {475-487},
     zbl = {1217.05177},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1508}
}

Ermelinda Delaviña; Ryan Pepper; Bill Waller. Lower bounds for the domination number. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 475-487. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1508/

[000] [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing, 1976). | Zbl 1226.05083

[001] [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, 1990). | Zbl 0688.05017

[002] [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. | Zbl 1114.05071

[003] [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. | Zbl 0644.05029

[004] [5] E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. | Zbl 0447.05039

[005] [6] P. Dankelmann, Average distance and the independence number, Discrete Appl. Math. 51 (1994) 73-83, doi: 10.1016/0166-218X(94)90095-7. | Zbl 0803.05020

[006] [7] P. Dankelmann, Average distance and the domination number, Discrete Appl. Math. 80 (1997) 21-35, doi: 10.1016/S0166-218X(97)00067-X. | Zbl 0888.05024

[007] [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. | Zbl 1134.05070

[008] [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. | Zbl 1211.05105

[009] [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. | Zbl 0982.05044

[010] [11] P. Erdös, M. Saks and V. Sós, Maximum Induced Tress in Graphs, J. Graph Theory 41 (1986) 61-79.

[011] [12] S. Fajtlowicz and W. Waller, On two conjectures of Graffiti, Congr. Numer. 55 (1986) 51-56. | Zbl 0639.05040

[012] [13] S. Fajtlowicz, Written on the Wall (manuscript), Web address: http://math.uh.edu/siemion.

[013] [14] S. Fajtlowicz, A Characterization of Radius-Critical Graphs, J. Graph Theory 12 (1988) 529-532, doi: 10.1002/jgt.3190120409. | Zbl 0713.05037

[014] [15] O. Favaron, M. Maheo and J-F. Sacle, Some Results on Conjectures of Graffiti - 1, Ars Combin. 29 (1990) 90-106. | Zbl 0743.05061

[015] [16] M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Co. (New York, Bell Telephone Lab., 1979).

[016] [17] P. Hansen, A. Hertz, R. Kilani, O. Marcotte and D. Schindl, Average distance and maximum induced forest, pre-print, 2007. | Zbl 1182.05049

[017] [18] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998). | Zbl 0890.05002

[018] [19] T. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, Inc., NY, 1998). | Zbl 0883.00011

[019] [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. | Zbl 1063.05035

[020] [21] L. Lovász and M.D. Plummer, Matching Theory (Acedemic Press, New York, 1986).

[021] [22] D.B. West, Open problems column #23, SIAM Activity Group Newsletter in Discrete Mathematics, 1996.

[022] [23] D.B. West, Introduction to Graph Theory (2nd ed.) (Prentice-Hall, NJ, 2001).