Edge Growth in Graph Cubes

Abstract

We show that for every connected graph $G$ of diameter $\ge 3$, the graph $G^3$ has average degree $\ge 7/4\delta (G)$. We also provide an example showing that this bound is best possible. This resolves a question of Hegarty \cite{PH}.

References in corpus (1)

• A Cauchy-Davenport type result for arbitrary regular graphs