Growth of graph powers

A. Pokrovskiy

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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).$

Détail

DOI : 10.37236/575

Classification : 05C12