Eigenvalues and cycles of consecutive lengths

DOI10.1002/JGT.22930MaRDI QIDQ6074592zbMATH OpenOpenAlexFDO

Authors Binlong Li, Bo Ning

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2110.05670

zbMATH Keywords

spectral radiusRamsey theorycycles

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38) Ramsey theory (05D10)

Abstract: As the counterpart of classical theorems on cycles of consecutive lengths due to Bondy and Bollob'as in spectral graph theory, Nikiforov proposed the following open problem in 2008: What is the maximum $C$ such that for all positive $varepsilon<C$ and sufficiently large $n$, every graph $G$ of order $n$ with spectral radius $ho(G)>sqrtlfloorfrac{n}^{2}4floor$ contains a cycle of length $ell$ for each integer $ellin[3,(C-varepsilon)n]$. We prove that $Cgeqfrac14$ by a novel method, improving the existing bounds. Besides several novel ideas, our proof technique is partly inspirited by the recent research on Ramsey numbers of star versus large even cycles due to Allen, {L}uczak, Polcyn and Zhang, and with aid of a powerful spectral inequality. We also derive an ErdH{o}s-Gallai-type edge number condition for even cycles, which may be of independent interest.

Recommendations

• The spectral radius of graphs without long cycles
• Spectral radius, edge-disjoint cycles and cycles of the same length
• A spectral condition for odd cycles in graphs
• The spectral radius of graphs without paths and cycles of specified length
• Stability of Woodall's theorem and spectral conditions for large cycles

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3570494 (Why is no real title available?)
• A conjecture on the spectral radius of graphs
• A note on cycle lengths in graphs
• A spectral condition for odd cycles in graphs
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• Arc coverings of graphs
• Bounds of eigenvalues of graphs
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Pancyclic graphs. I
• Sharp upper bounds of the spectral radius of a graph

Cited in

(9)

• A spectral condition for odd cycles in graphs
• The spectral radius of graphs without long cycles
• Stability of Woodall's theorem and spectral conditions for large cycles
• On some papers of Nikiforov.
• The maximum number of cliques in graphs with bounded odd circumference
• Note on Mantel theorem and Turán theorem
• Length and Eigenvalue Equivalence
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs

This page was built for publication: Eigenvalues and cycles of consecutive lengths

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