## Abstract

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 [Formula presented], and the radius is at most [Formula presented], where n is the order and δ the minimum degree of G. If δ−1 is a prime power, then both bounds are sharp apart from an additive constant. For graphs of large maximum degree Δ, we show that these bounds can be improved to [Formula presented] for the diameter, and [Formula presented] 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 δ,Δ∈N with Δ≥δ let n(δ,Δ,g) be the minimum order of a graph of girth g, minimum degree δ and maximum degree Δ. Then [Formula presented]. If δ−1 is a prime power, then there exist infinitely many values of Δ such that, for δ constant and Δ large, n(δ,Δ,6)=δΔ+O(Δ).

Original language | English |
---|---|

Pages (from-to) | 125-137 |

Number of pages | 13 |

Journal | Discrete Applied Mathematics |

Volume | 294 |

DOIs | |

Publication status | Published - 15 May 2021 |

## Keywords

- Cage
- Diameter
- Generalised cage
- Girth
- Minimum degree
- Radius

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics