Radius, Girth and Minimum Degree

Abstract

Given a connected graph $G$ on $n$ vertices, with minimum degree $\delta \ge 2$ and girth at least $g\ge 4$, what is the maximum radius $r$ this graph can have? Erdős, Pach, Pollack and Tuza established in the triangle-free case ($g=4$) that $r\le \frac{n-2}{\delta }+12$, and noted that up to the value of the additive constant, this is tight. We determine the exact value for the triangle-free case. For higher $g$ little is known. We settle the order of $r$ for $g=6,8,12$ and prove an upper bound to the order for general even $g$. Finally, we show that proving the corresponding lower bound for general even $g$ is equivalent to the Erdős girth conjecture.

11 pages