科研之友
微信
新浪微博
Facebook
分享链接
摘要
The kth power of a simple graph G, denoted by Gk, is the graph with vertex set V(G) where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of Gk. Here we prove that if G is connected with minimum degree d=2 and |V(G)|=83d, then G4 has average degree at least 73d. We also prove that if G is a connected d-regular graph on n vertices with diameter at least 3k+3, then the average degree of G3k+2 is at least (2k+1)(d+1)-k(k+1)(d+1)2/n-1.Both these results are shown to be essentially best possible; the second is best possible even when n/d is arbitrarily large.
- 出版日期2013-1
