Growth of graph powers (Q540085)

Summary: For a graph \(G\), its \(r\)th 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 \(r\)th power. In particular we obtain that, for \(r \geq 3\), either the \(r\)th power is complete or ``many'' new edges are added. In this direction, Hegarty showed that there is a constant \(\epsilon > 0\) such \(e(G^3) \geq (1 + \epsilon)e(G)\). We extend this result in two directions. We give an alternative proof of Hegarty's result with an improved constant of \(\epsilon = 1\). We also show that for general \(r, e(G^r) \geq (\lceil \frac{r}{3}\rceil-1) e(G)\).