# Domination and leaf density in graphs

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 3, page 251-259
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAnders Sune Pedersen. "Domination and leaf density in graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 251-259. <http://eudml.org/doc/270202>.

@article{AndersSunePedersen2005,

abstract = {The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for the total domination number and the partition domination number.},

author = {Anders Sune Pedersen},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {bounds; domination number; leaves; partioned domination; total domination number; partition domination; extremal graphs},

language = {eng},

number = {3},

pages = {251-259},

title = {Domination and leaf density in graphs},

url = {http://eudml.org/doc/270202},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Anders Sune Pedersen

TI - Domination and leaf density in graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 3

SP - 251

EP - 259

AB - The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are obtained for the total domination number and the partition domination number.

LA - eng

KW - bounds; domination number; leaves; partioned domination; total domination number; partition domination; extremal graphs

UR - http://eudml.org/doc/270202

ER -

## References

top- [1] R.C. Brigham, J.R. Carrington and R.P. Vitray, Connected graphs with maximum total domination number, J. Combin. Math. Combin. Comput. 34 (2000) 81-95. Zbl0958.05100
- [2] E.J. Cockayne, R.M. Dawes and S.T. Hedetniemi, Total domination in graphs, Networks 10 (1980) 211-219, doi: 10.1002/net.3230100304. Zbl0447.05039
- [3] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079. Zbl0602.05043
- [4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979). Zbl0411.68039
- [5] B.L. Hartnell and P.D. Vestergaard, Partitions and domination in a graph, J. Combin. Math. Combin. Comput. 46 (2003) 113-128. Zbl1036.05039
- [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., 1998). Zbl0890.05002
- [7] A.M. Henning and P.D. Vestergaard, Domination in partitioned graphs with minimum degree two (Manuscript, 2002). Zbl1113.05077
- [8] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 1962).
- [9] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
- [10] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congr. Numer. 132 (1998) 85-91. Zbl0951.05079
- [11] Z. Tuza and P.D. Vestergaard, Domination in partitioned graphs, Discuss. Math. Graph Theory 22 (2002) 199-210, doi: 10.7151/dmgt.1169. Zbl1016.05057

## NotesEmbed ?

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