Radius, girth and minimum degree

Abstract

Abstract: The objective of the present paper is to study the maximum radius r of a connected graph of order n , minimum degree δ ≥ 2 and girth at least g ≥ 4 . Erdős, Pach, Pollack and Tuza proved that if g = 4 , that is, the graph is triangle‐free, then r ≤ n − 2 δ + 12 , and noted that up to the value of the additive constant, this upper bound is tight. In this paper we shall determine the exact maximum. For larger values of g little is known. We settle the order of the maximum r for g = 6 , 8 and 12, and prove an upper bound for every even g , which we conjecture to be tight up to a constant factor. Finally, we show that our conjecture implies the so‐called Erdős girth conjecture.