Stability version of Dirac's theorem and its applications for generalized Turán problems

Xiutao Zhu; Ervin Győri; Zhen He; Zequn Lv; Nika Salia; Chuanqi Xiao

doi:10.1112/blms.12823

Stability version of Dirac's theorem and its applications for generalized Turán problems

Xiutao Zhu
, Ervin Győri^*
, Zhen He
, Zequn Lv
, Nika Salia
, Chuanqi Xiao

^*Corresponding author for this work

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

4 Scopus citations

Abstract

In 1952, Dirac proved that every 2-connected (Formula presented.) -vertex graph with the minimum degree (Formula presented.) contains a cycle of length at least (Formula presented.). Here we obtain a stability version of this result by characterizing those graphs with minimum degree (Formula presented.) and circumference at most (Formula presented.). We present applications of the above-stated result by obtaining generalized Turán numbers. In particular, for all (Formula presented.) we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has a circumference larger than (Formula presented.). In addition, we give a new proof of Luo's theorem for cliques using our stability result.

Original language	English
Pages (from-to)	1857-1873
Number of pages	17
Journal	Bulletin of the London Mathematical Society
Volume	55
Issue number	4
DOIs	https://doi.org/10.1112/blms.12823
State	Published - Aug 2023
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2023 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence.

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1112/blms.12823

Cite this

@article{6112c7bd8e904f57af93e025d5516817,

title = "Stability version of Dirac's theorem and its applications for generalized Tur{\'a}n problems",

abstract = "In 1952, Dirac proved that every 2-connected (Formula presented.) -vertex graph with the minimum degree (Formula presented.) contains a cycle of length at least (Formula presented.). Here we obtain a stability version of this result by characterizing those graphs with minimum degree (Formula presented.) and circumference at most (Formula presented.). We present applications of the above-stated result by obtaining generalized Tur{\'a}n numbers. In particular, for all (Formula presented.) we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has a circumference larger than (Formula presented.). In addition, we give a new proof of Luo's theorem for cliques using our stability result.",

author = "Xiutao Zhu and Ervin Gy{\H o}ri and Zhen He and Zequn Lv and Nika Salia and Chuanqi Xiao",

note = "Publisher Copyright: {\textcopyright} 2023 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence.",

year = "2023",

month = aug,

doi = "10.1112/blms.12823",

language = "English",

volume = "55",

pages = "1857--1873",

journal = "Bulletin of the London Mathematical Society",

issn = "0024-6093",

number = "4",

}

TY - JOUR

T1 - Stability version of Dirac's theorem and its applications for generalized Turán problems

AU - Zhu, Xiutao

AU - Győri, Ervin

AU - He, Zhen

AU - Lv, Zequn

AU - Salia, Nika

AU - Xiao, Chuanqi

PY - 2023/8

Y1 - 2023/8

N2 - In 1952, Dirac proved that every 2-connected (Formula presented.) -vertex graph with the minimum degree (Formula presented.) contains a cycle of length at least (Formula presented.). Here we obtain a stability version of this result by characterizing those graphs with minimum degree (Formula presented.) and circumference at most (Formula presented.). We present applications of the above-stated result by obtaining generalized Turán numbers. In particular, for all (Formula presented.) we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has a circumference larger than (Formula presented.). In addition, we give a new proof of Luo's theorem for cliques using our stability result.

AB - In 1952, Dirac proved that every 2-connected (Formula presented.) -vertex graph with the minimum degree (Formula presented.) contains a cycle of length at least (Formula presented.). Here we obtain a stability version of this result by characterizing those graphs with minimum degree (Formula presented.) and circumference at most (Formula presented.). We present applications of the above-stated result by obtaining generalized Turán numbers. In particular, for all (Formula presented.) we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has a circumference larger than (Formula presented.). In addition, we give a new proof of Luo's theorem for cliques using our stability result.

UR - https://www.scopus.com/pages/publications/85150860414

U2 - 10.1112/blms.12823

DO - 10.1112/blms.12823

M3 - Article

AN - SCOPUS:85150860414

SN - 0024-6093

VL - 55

SP - 1857

EP - 1873

JO - Bulletin of the London Mathematical Society

JF - Bulletin of the London Mathematical Society

IS - 4

ER -

Stability version of Dirac's theorem and its applications for generalized Turán problems

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this