Average Degree in Graph Powers
Matt DeVos, Jessica M. McDonald, Diego Scheide · Journal of Graph Theory · 2012
Abstract 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 urn:x-wiley:03649024:jgt21628:equation:jgt21628-math-0009 Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.