Domination and leaf density in graphs

Anders 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 -