Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Domination and leaf density in graphs

Anders Sune Pedersen — 2005

Discussiones Mathematicae Graph Theory

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

Page 1

Download Results (CSV)