Eigenvalues and cycles of consecutive lengths

DOI10.1002/JGT.22930zbMATH Open1522.05279arXiv2110.05670OpenAlexW4316039737MaRDI QIDQ6074592FDOQ6074592

Authors: Binlong Li, Bo Ning 

Publication date: 12 October 2023

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

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.

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

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

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)

Cites Work

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

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)