科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a connected graph of order n and independence number alpha. We prove that G has a spanning tree with average distance at most 23 alpha, if n <= 2 alpha-1, and at most alpha+2, if n>2 alpha-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.
- 出版日期2014-7
