\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf A. Pokrovskiy}
%
%
\medskip
\noindent
%
%
{\bf Growth of Graph Powers}
%
%
\vskip 5mm
\noindent
%
%
%
%
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).$
\end{document}