Premium
Radius, girth and minimum degree
Author(s) -
Dvorák Vojtĕch,
Hintum Peter,
Shaw Amy,
Tiba Marius
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22790
Subject(s) - mathematics , combinatorics , conjecture , upper and lower bounds , girth (graph theory) , constant (computer programming) , graph , degree (music) , radius , order (exchange) , collatz conjecture , discrete mathematics , mathematical analysis , physics , computer security , finance , computer science , acoustics , economics , programming language
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.