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

DOI10.1112/BLMS.12823MaRDI QIDQ6096834zbMATH OpenOpenAlexWikidataFDO

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

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.12465, http://real.mtak.hu/162689/1/2207.12465v2.pdf

zbMATH Keywords

generalized Turán numbers

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

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

Recommendations

• Some Stability and Exact Results in Generalized Turán Problems
• Exact stability for Turán's theorem
• On supersaturation and stability for generalized Turán problems
• Stability of solutions for an abstract Dirichlet problem
• Perturbation of Dirichlet forms and stability of fundamental solutions
• An extension of Turán's theorem, uniqueness and stability
• A stability version of the Gauss-Lucas theorem and applications
• On stability of generalized Cauchy-type problem
• A general stability theorem with applications
• Note on the stability of the Dirichlet problem and the Poisson equation

Cites work

• A note on the maximum number of triangles in a C₅‐free graph
• A strengthening of Erdős-Gallai theorem and proof of Woodall's conjecture
• Additive approximation of generalized Turán questions
• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• Many \(T\) copies in \(H\)-free graphs
• On maximal paths and circuits of graphs
• On the maximal number of certain subgraphs in \(K_ r\)-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the maximum number of odd cycles in graphs without smaller odd cycles
• On the number of pentagons in triangle-free graphs
• Pentagons vs. triangles
• Some Theorems on Abstract Graphs
• Stability in the Erdős-Gallai theorem on cycles and paths. II
• Stability in the Erdős-Gallai theorems on cycles and paths
• Stability results on the circumference of a graph
• The maximum number of P_\ell copies in P_k-free graphs
• The maximum number of cliques in graphs without long cycles
• The maximum number of triangles in \(C_{2k+1}\)-free graphs

Cited in

(9)

• On supersaturation and stability for generalized Turán problems
• The maximum number of triangles in \(F_k\)-free graphs
• On a property of 2-connected graphs and Dirac's theorem
• The maximum number of cliques in graphs with bounded odd circumference
• Stability in Bondy's theorem on paths and cycles
• Extremal problems for a matching and any other graph
• The number of stars in a graph that forbids a matching and any graph
• Exact results for generalized Turán number of a linear forest and a clique
• Stability results on the circumference of a graph

This page was built for publication: Stability version of Dirac's theorem and its applications for generalized Turán problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096834)