Geodesic
Lower bounds for the domination number
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 475-487.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2010_30_3_a9,
     author = {Delavi\~na, Ermelinda and Pepper, Ryan and Waller, Bill},
     title = {Lower bounds for the domination number},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {475--487},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a9/}
}
TY  - JOUR
AU  - Delaviña, Ermelinda
AU  - Pepper, Ryan
AU  - Waller, Bill
TI  - Lower bounds for the domination number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 475
EP  - 487
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a9/
LA  - en
ID  - DMGT_2010_30_3_a9
ER  - 
%0 Journal Article
%A Delaviña, Ermelinda
%A Pepper, Ryan
%A Waller, Bill
%T Lower bounds for the domination number
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 475-487
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a9/
%G en
%F DMGT_2010_30_3_a9
Delaviña, Ermelinda; Pepper, Ryan; Waller, Bill. Lower bounds for the domination number. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 3, pp. 475-487. http://geodesic.mathdoc.fr/item/DMGT_2010_30_3_a9/

[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).