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
Access Full Article
topAbstract
topHow to cite
topErmelinda 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] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier Publishing, 1976). Zbl1226.05083
- [2] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, 1990). Zbl0688.05017
- [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] 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] E. Cockayne, R. Dawes and S. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. Zbl0447.05039
- [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] 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] 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] 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] 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] 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. Zbl0639.05040
- [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. Zbl0713.05037
- [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] 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. Zbl1182.05049
- [18] T. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Decker, Inc., NY, 1998). Zbl0890.05002
- [19] T. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Decker, Inc., NY, 1998). Zbl0883.00011
- [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] 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).
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.