Distances in graphs of girth 6 and generalised cages

In this paper we present bounds on the radius and diameter of graphs of girth at least 6 and for (C-4, C-5)-free graphs, i.e., graphs not containing cycles of length 4 or 5. We show that the diameter of a graph G of girth at least 6 is at most 3n/delta(2)-delta+1 - 1 and the radius is at most 3n/2(delta(2)-delta+1) + 10, where n is the order and delta the minimum degree of G. If delta - 1 is a prime power, then both bounds are sharp apart from an additive constant. For graphs of large maximum degree Delta, we show that these bounds can be improved to 3n-Delta delta/delta(2)-delta+1 - 3(delta-1)root Delta(delta-2)/delta(2)-delta+1 + 10 for the diameter, and 3n-3 Delta delta/2(delta(2)-delta+1) - 3(delta-1)root Delta(delta-2)/2(delta(2)-delta+1) + 22 for the radius. We further show that only slightly weaker bounds hold for (C-4, C-5)-free graphs. As a by-product we obtain a result on a generalisation of cages. For given delta, Delta is an element of N with Delta >= delta let n(delta, Delta, g) be the minimum order of a graph of girth g, minimum degree delta and maximum degree Delta. Then n(delta, Delta, 6) >= Delta delta + (delta - 1)root Delta(delta - 2) + 3/2 If delta - 1 is a prime power, then there exist infinitely many values of Delta such that, for delta constant and Delta large, n(delta, Delta, 6) = delta Delta + O(root Delta). (C) 2021 Elsevier B.V. All rights reserved.