Growth of graph powers

Abstract

For a graph G, its rth power is constructed by placing an edge between two vertices if they are within distance r of each other. In this note we study the amount of edges added to a graph by taking its rth power. In particular we obtain that either the rth power is complete or "many" new edges are added. This is an extension of a result obtained by P. Hegarty for cubes of graphs.

6 pages, 1 figure

References in corpus (2)

• A Summary of Problems and Results related to the Caccetta-Haggkvist Conjecture
• A Cauchy-Davenport type result for arbitrary regular graphs

Cited by in corpus (1)

• Average Degree in Graph Powers