Cycles of Many Lengths in Hamiltonian Graphs

Matija Bucić; Lior Gishboliner; Benny Sudakov

doi:10.1007/978-3-030-83823-2_57

Cycles of Many Lengths in Hamiltonian Graphs

Matija Bucić, Lior Gishboliner, Benny Sudakov

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

In 1999, Jacobson and Lehel conjectured that for k≥ 3, every k-regular Hamiltonian graph has cycles of at least linearly many different lengths. This was further strengthened by Verstraëte, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least 3. Despite attention from various researchers, until now the best partial result towards both of these conjectures was a n lower bound on the number of cycle lengths. We resolve these conjectures asymptotically, by showing that the number of cycle lengths is at least n¹ ^- ^o ⁽ ¹ ⁾.

Original language	English (US)
Title of host publication	Trends in Mathematics
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	366-372
Number of pages	7
DOIs	https://doi.org/10.1007/978-3-030-83823-2_57
State	Published - 2021
Externally published	Yes

Publication series

Name	Trends in Mathematics
Volume	14
ISSN (Print)	2297-0215
ISSN (Electronic)	2297-024X

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Cycle lengths
Cycle spectrum
Hamiltonian graph

Access to Document

10.1007/978-3-030-83823-2_57

Cite this

@inbook{4fa506a74b404a318a57bb231218c77c,

title = "Cycles of Many Lengths in Hamiltonian Graphs",

abstract = "In 1999, Jacobson and Lehel conjectured that for k≥ 3, every k-regular Hamiltonian graph has cycles of at least linearly many different lengths. This was further strengthened by Verstra{\"e}te, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least 3. Despite attention from various researchers, until now the best partial result towards both of these conjectures was a n lower bound on the number of cycle lengths. We resolve these conjectures asymptotically, by showing that the number of cycle lengths is at least n1 - o ( 1 ).",

keywords = "Cycle lengths, Cycle spectrum, Hamiltonian graph",

author = "Matija Buci{\'c} and Lior Gishboliner and Benny Sudakov",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-83823-2_57",

language = "English (US)",

series = "Trends in Mathematics",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "366--372",

booktitle = "Trends in Mathematics",

address = "Germany",

}

TY - CHAP

T1 - Cycles of Many Lengths in Hamiltonian Graphs

AU - Bucić, Matija

AU - Gishboliner, Lior

AU - Sudakov, Benny

PY - 2021

Y1 - 2021

N2 - In 1999, Jacobson and Lehel conjectured that for k≥ 3, every k-regular Hamiltonian graph has cycles of at least linearly many different lengths. This was further strengthened by Verstraëte, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least 3. Despite attention from various researchers, until now the best partial result towards both of these conjectures was a n lower bound on the number of cycle lengths. We resolve these conjectures asymptotically, by showing that the number of cycle lengths is at least n1 - o ( 1 ).

AB - In 1999, Jacobson and Lehel conjectured that for k≥ 3, every k-regular Hamiltonian graph has cycles of at least linearly many different lengths. This was further strengthened by Verstraëte, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least 3. Despite attention from various researchers, until now the best partial result towards both of these conjectures was a n lower bound on the number of cycle lengths. We resolve these conjectures asymptotically, by showing that the number of cycle lengths is at least n1 - o ( 1 ).

KW - Cycle lengths

KW - Cycle spectrum

KW - Hamiltonian graph

UR - http://www.scopus.com/inward/record.url?scp=85114085553&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85114085553&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-83823-2_57

DO - 10.1007/978-3-030-83823-2_57

M3 - Chapter

AN - SCOPUS:85114085553

T3 - Trends in Mathematics

SP - 366

EP - 372

BT - Trends in Mathematics

PB - Springer Science and Business Media Deutschland GmbH

ER -

Cycles of Many Lengths in Hamiltonian Graphs

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this