Edge Growth in Graph Cubes
Matt DeVos, Stéphan Thomassé · arXiv (Cornell University) · 2010
We show that for every connected graph $G$ of diameter $\ge 3$, the graph $G^3$ has average degree $\ge 7/4 δ(G)$. We also provide an example showing that this bound is best possible. This resolves a question of Hegarty \cite{PH}.