𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Average distance and independence number

✍ Scribed by P. Dankelmann

Book ID
104183140
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
493 KB
Volume
51
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The average distance and the independenc
The average distance and the independence number
✍ F. R. K. Chung πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 258 KB

We prove that in every connected graph the independence number is at least as large as the average distance between vertices. Theorem. For every connected graph G , we have a ( G ) 2 D ( G ) , with equality if and only if G is a complete graph.

Average distance and domination number
Average distance and domination number
✍ P. Dankelmann πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 846 KB

We give a sharp upper bound on the average distance of a graph of given order and domination number and determine the extremal graphs.

Independence, odd girth, and average deg
Independence, odd girth, and average degree
✍ Christian LΓΆwenstein,; Anders Sune Pedersen,; Dieter Rautenbach;; Friedrich Rege πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 187 KB

We prove several tight lower bounds in terms of the order and the average degree for the independence number of graphs that are connected and/or satisfy some odd girth condition. Our main result is the extension of a lower bound for the independence number of triangle-free graphs of maximum degree a