Geodesic
Domination and leaf density in graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 251-259

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

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.
Keywords: bounds, domination number, leaves, partioned domination, total domination number 
Pedersen, Anders. Domination and leaf density in graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 251-259. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a3/
@article{DMGT_2005_25_3_a3,
     author = {Pedersen, Anders},
     title = {Domination and leaf density in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {251--259},
     year = {2005},
     volume = {25},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a3/}
}
TY  - JOUR
AU  - Pedersen, Anders
TI  - Domination and leaf density in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 251
EP  - 259
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a3/
LA  - en
ID  - DMGT_2005_25_3_a3
ER  - 
%0 Journal Article
%A Pedersen, Anders
%T Domination and leaf density in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 251-259
%V 25
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a3/
%G en
%F DMGT_2005_25_3_a3

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

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

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

[4] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness (Freeman, New York, 1979).

[5] B.L. Hartnell and P.D. Vestergaard, Partitions and domination in a graph, J. Combin. Math. Combin. Comput. 46 (2003) 113-128.

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., 1998).

[7] A.M. Henning and P.D. Vestergaard, Domination in partitioned graphs with minimum degree two (Manuscript, 2002).

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

[10] S.M. Seager, Partition dominations of graphs of minimum degree 2, Congr. Numer. 132 (1998) 85-91.

[11] Z. Tuza and P.D. Vestergaard, Domination in partitioned graphs, Discuss. Math. Graph Theory 22 (2002) 199-210, doi: 10.7151/dmgt.1169.