Repository logo
 

Radius, girth and minimum degree

Published version
Peer-reviewed

Change log

Authors

Dvorák, V 
van Hintum, P 
Shaw, A 
Tiba, M 

Abstract

jats:titleAbstract</jats:title>jats:pThe objective of the present paper is to study the maximum radius of a connected graph of order , minimum degree and girth at least . Erdős, Pach, Pollack and Tuza proved that if , that is, the graph is triangle‐free, then , 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 little is known. We settle the order of the maximum for and 12, and prove an upper bound for every even , 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.</jats:p>

Description

Funder: UK Research and Innovation; Id: http://dx.doi.org/10.13039/100014013


Funder: Cambridge Trust


Funder: University of Cambridge; Id: http://dx.doi.org/10.13039/501100000735

Keywords

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

Journal of Graph Theory

Conference Name

Journal ISSN

0364-9024
1097-0118

Volume Title

Publisher

Wiley