𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independence and average distance in graphs

✍ Scribed by Peter Firby; Julie Haviland

Book ID
104294735
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
628 KB
Volume
75
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Average distance in colored graphs
Average distance in colored graphs
✍ Peter Dankelmann; Wayne Goddard; Peter Slater πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 143 KB

## Abstract For a graph __G__ where the vertices are colored, the __colored distance__ of __G__ is defined as the sum of the distances between all unordered pairs of vertices having different colors. Then for a fixed supply __s__ of colors, __d~s~(G)__ is defined as the minimum colored distance ove

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.