Radius, girth and minimum degree. Issue 3 (9th January 2022)

• Record Type: Journal Article
• Authors: Dvorák, Vojtĕch; van Hintum, Peter; Shaw, Amy; Tiba, Marius
• Is Part Of: Journal of graph theory. Volume 100:Issue 3(2022)
• Page Start: 470
• Page End: 488
• Publication Date: 2022-01-09
• Subjects: extremal graph theory -- girth -- minimum degree -- radius -- triangle‐free graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22790
• Languages: English
• ISSNs: 0364-9024

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.