A variation of a theorem by Pósa

Zoltán Füredi; Alexandr Kostochka; Ruth Luo

doi:10.1016/j.disc.2019.03.008

A variation of a theorem by Pósa

Zoltán Füredi, Alexandr Kostochka, Ruth Luo

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.

Original language	English (US)
Pages (from-to)	1919-1923
Number of pages	5
Journal	Discrete Mathematics
Volume	342
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2019.03.008
State	Published - Jul 2019

Keywords

Extremal graph theory
Hamiltonian cycles
Turán problem

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2019.03.008

Library availability

Discover UIUC Full Text

Cite this

@article{a95ccea9ca9d466cb0b0bad26aeac2c5,

title = "A variation of a theorem by P{\'o}sa",

abstract = "A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.",

keywords = "Extremal graph theory, Hamiltonian cycles, Tur{\'a}n problem",

author = "Zolt{\'a}n F{\"u}redi and Alexandr Kostochka and Ruth Luo",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2019",

month = jul,

doi = "10.1016/j.disc.2019.03.008",

language = "English (US)",

volume = "342",

pages = "1919--1923",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - A variation of a theorem by Pósa

AU - Füredi, Zoltán

AU - Kostochka, Alexandr

AU - Luo, Ruth

PY - 2019/7

Y1 - 2019/7

N2 - A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.

AB - A graph G is ℓ-hamiltonian if each linear forest F with ℓ edges contained in G can be extended to a hamiltonian cycle of G. We give a sharp upper bound for the maximum number of cliques of a fixed size in a non-ℓ-hamiltonian graph. Furthermore, we prove stability: if a non-ℓ-hamiltonian graph contains almost the maximum number of cliques, then it is a subgraph of one of two extremal graphs.

KW - Extremal graph theory

KW - Hamiltonian cycles

KW - Turán problem

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

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

U2 - 10.1016/j.disc.2019.03.008

DO - 10.1016/j.disc.2019.03.008

M3 - Article

AN - SCOPUS:85064261923

SN - 0012-365X

VL - 342

SP - 1919

EP - 1923

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

ER -

A variation of a theorem by Pósa

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this