# Domination and leaf density in graphs

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

top

## Abstract

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

## How to cite

top

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

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. [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. [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. [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. [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. [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. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., 1998). Zbl0890.05002
7. [7] A.M. Henning and P.D. Vestergaard, Domination in partitioned graphs with minimum degree two (Manuscript, 2002). Zbl1113.05077
8. [8] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ., 1962).
9. [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. [10] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congr. Numer. 132 (1998) 85-91. Zbl0951.05079
11. [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?

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.