Average Degree in Graph Powers
The kth power of a simple graph G, denoted by , is the graph with vertex set 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 . Here we prove that if G is connected with minimum degree and , then G4 has average degree at least . We also prove that if G is a connected d-regular graph on n vertices with diameter at least , then the average degree of is at least
average degree graph power