Average Degree in Graph Powers

The k th power of a simple graph G , denoted by 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 least7 3 d . We also prove that if G is a connected d ‐regular graph on n vertices with diameter at least 3 k + 3 , then the average degree of G 3 k + 2is at least( 2 k + 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.