Growth of Graph Powers

A. Pokrovskiy

Abstract


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 = \frac{1}{6}$. We also show that for general $r$, $e(G^{r}) \geq \left( \left\lceil \frac{r}{3} \right\rceil -1 \right)e(G).$


Full Text: PDF