Average Distance, Independence Number, and Spanning Trees

Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n>2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in t...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2014-07, Vol.76 (3), p.194-199
Main Author: Mukwembi, Simon
Format: Article
Language:English
Subjects:
average distance
independence number
spanning trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most 23α, if n≤2α−1, and at most α+2, if n>2α−1. As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.21758