Show simple item record

dc.contributor.authorDvorák, V
dc.contributor.authorvan Hintum, P
dc.contributor.authorShaw, A
dc.contributor.authorTiba, M
dc.date.accessioned2022-01-10T12:51:46Z
dc.date.available2022-01-10T12:51:46Z
dc.date.issued2022-01-09
dc.date.submitted2021-02-09
dc.identifier.issn0364-9024
dc.identifier.otherjgt22790
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/332567
dc.descriptionFunder: UK Research and Innovation; Id: http://dx.doi.org/10.13039/100014013
dc.descriptionFunder: Cambridge Trust
dc.descriptionFunder: University of Cambridge; Id: http://dx.doi.org/10.13039/501100000735
dc.description.abstractAbstract: 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.
dc.languageen
dc.publisherWiley
dc.subjectARTICLE
dc.subjectARTICLES
dc.subjectextremal graph theory
dc.subjectgirth
dc.subjectminimum degree
dc.subjectradius
dc.subjecttriangle‐free graphs
dc.titleRadius, girth and minimum degree
dc.typeArticle
dc.date.updated2022-01-10T12:51:46Z
prism.publicationNameJournal of Graph Theory
dc.identifier.doi10.17863/CAM.80017
dcterms.dateAccepted2021-12-20
rioxxterms.versionofrecord10.1002/jgt.22790
rioxxterms.versionAO
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://creativecommons.org/licenses/by/4.0/
dc.identifier.eissn1097-0118
cam.issuedOnline2022-01-09


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record