Average Degree in Graph Powers

Details Average Degree in Graph Powers Average Degree in Graph Powers

2010-12-14

arxiv.org/abs/1012.2950v1

Mathematics

Combinatorics

14 pages, 3 figures

Scientific paper

The kth power of a simple graph G, denoted G^k, 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 G^k. Here we prove that if G is connected with minimum degree d > 2 and |V(G)| > (8/3)d, then G^4 has average degree at least (7/3)d. 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 G^{3k+2} is at least (2k+1)(d+1) - k(k+1) (d+1)^2/n - 1. Both of these results are shown to be essentially best possible; the second is best possible even when n/d is arbitrarily large.

Affiliated with

Also associated with

No associations

Rating

Average Degree in Graph Powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Average Degree in Graph Powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Average Degree in Graph Powers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178987