The stability method, eigenvalues and cycles of consecutive lengths

2021/02/07 by Binlong Li, Bo Ning, Li, Binlong +1 · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Graph theory and applications #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2102.03855

Abstract

Woodall proved that for a graph G of order n≥ 2k+3 where k≥ 0 is an integer, if e(G)≥ \binomn-k-12+\binomk+22+1 then G contains a C_ℓ for each ℓ∈ [3,n-k]. In this article, we prove a stability result of this theorem. As a byproduct, we give complete solutions to two problems in \citeGN19. Our second part is devoted to an open problem by Nikiforov: what is the maximum C such that for all positive ε√(\lfloor(n²)/(4)\rfloor) contains a cycle of length ℓ for every ℓ≤ (C-ε)n. We prove that C≥(1)/(4) by a method different from previous ones, improving the existing bounds. We also derive an Erdős-Gallai type edge number condition for even cycles, which may be of independent interest.

Cited by

• Spectral extrema of K_s,t-minor free graphs--On a conjecture of M. Tait

Related

• Eigenvalues and cycles of consecutive lengths
• Stability in the Erdős--Gallai Theorem on cycles and paths, II
• Upper bounds on the extremal number of the 4-cycle
• On graphs without cycles of length 1 modulo 3
• Cycle-complete Ramsey numbers