A spectral condition for odd cycles in graphs

DOI10.1016/J.LAA.2007.09.029MaRDI QIDQ2477528zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 14 March 2008

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph spectral radiusodd cyclestabilitytriangle

Mathematics Subject Classification ID

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

Abstract: We give a sharp spectral condition for the existence of odd cycles in a graph of given order. We also prove a related stability result.

Review text

The following has been proven: Given a graph \(G\) of sufficiently large order \(n\). If the largest eigenvalue \(\mu(G)\) of its adjacency matrix satisfies \(\mu(G) > \sqrt{\lfloor n^2/4\rfloor}\) then \(G\) contains a cycle of length \(t\) for every \(t \leq n/320\). Moreover, the condition is sharp, i.e.\,the complete bipartite graph \(T_2(n)\) with parts of size \(\lfloor n/2\rfloor\) and \(\lceil n/2\rceil\) contains no odd cycles and its largest eigenvalue is equal to \(\sqrt{\lfloor n^2/4\rfloor}\). This condition is also stable, i.e. if \(\mu(G)\) is close to \(\sqrt{\lfloor n^2/4\rfloor}\) and \(G\) does not contain a cycle of length \(t\) for some \(t\leq n/321\), then \(G\) resembles \(T_2(n)\) (there exists an induced bipartite subgraph \(G_0 \subset G\) with \(| G_0| \) close to \(n\) and \(\delta(G_0)\) close to \(n/2\)).

Recommendations

• Adjacency eigenvalues of graphs without short odd cycles
• Eigenvalues and cycles of consecutive lengths
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• The spectral radius of graphs with no intersecting odd cycles
• Spectral conditions for the existence of specified paths and cycles in graphs

Cites work

• Bounds on graph eigenvalues. II
• Cliques and the spectral radius
• Cycle lengths in graphs with large minimum degree
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• On maximal paths and circuits of graphs

Cited in

(72)

• The maximum spectral radius of C₄-free graphs of given order and size
• Negative (and positive) circles in signed graphs: a problem collection
• Spectral extremal results with forbidding linear forests
• The signless Laplacian spectral radius of graphs with no intersecting triangles
• The extremal \(\alpha \)-index of graphs with no 4-cycle and 5-cycle
• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• A spectral condition for the existence of a pentagon in non-bipartite graphs
• Spectral radius, edge-disjoint cycles and cycles of the same length
• Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait
• The spectral Turán problem about graphs with no 6-cycle
• Generalized Turán problems for even cycles
• The spectral radius of graphs with no odd wheels
• A spectral condition for odd cycles in non-bipartite graphs
• Analytic methods for uniform hypergraphs
• Spectral conditions for the existence of specified paths and cycles in graphs
• The maximum spectral radius of wheel-free graphs
• A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size
• On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees
• Spectral extremal graphs for disjoint cliques
• Spectral radius conditions for the existence of all subtrees of diameter at most four
• Stability of Woodall's theorem and spectral conditions for large cycles
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• On the principal eigenvectors of uniform hypergraphs
• Extremal problems for the p-spectral radius of graphs
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• New results on -spectral radius of graphs
• A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs
• On the \(A_\alpha \)-spectral radius of graphs with given size
• A Spectral Erdős-Sós Theorem
• Eigenvalues and cycles of consecutive lengths
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs
• The index of signed graphs with forbidden subgraphs
• Spectral Turán problems for intersecting even cycles
• Spectral extremal problem on disjoint color-critical graphs
• Spectral extremal results on trees
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• On the spectral radius of graphs without a gem
• On the spectral Turán problem of theta graphs
• The spectral even cycle problem
• Spectral extremal problem on t copies of -cycles
• A spectral condition for component factors in graphs
• Spectral extremal problem of the p th power of cycles
• Spectral extremal problem for intersecting one even and one odd cycle
• A sharp spectral extremal result for general non-bipartite graphs
• A spectral generalized Alon-Frankl theorem
• Signless Laplacian spectral conditions for extremal quadrilateral and star embeddings
• Spectral extremal problem for the odd prism
• Spectral extremal problem on the fish graph
• A spectral version of the theorem of Zykov and Erdős
• Principal eigenvectors in hypergraph Turán problems
• On the spectral extremal problem of planar graphs
• Spectral extremal problems on outerplanar and planar graphs
• A spectral generalized Erdős-Gallai theorem
• Spectral extremal problems for non-bipartite graphs without odd cycles
• The maximum spectral radius of graphs of even size forbidding \(\{H(3, 3), H(4, 3)\}\)
• The largest eigenvalue of \(\mathcal{C}_k^-\)-free signed graphs
• Brualdi-Hoffman-Turán problem of the gem
• Long cycles and spectral radii in planar graphs
• The spectral Turán problem about graphs of given size with forbidden subgraphs
• Spectral Turán problem of non-bipartite graphs: forbidden books
• Maximum \(A_\alpha\)-spectral radius of \(\{C(3, 3), C(4, 3)\}\)-free graphs
• The maximum spectral radius of k P₃-free graphs
• Some Turán-type results for the signless Laplacian spectral radius
• A spectral Turán problem for a fixed tree
• A general theorem in spectral extremal graph theory
• On A_ spectral extremal problems of outerplanar graphs
• Bounds on the spectral radii of Berge C₅-free linear r-graphs
• The spectra of multiplicative attribute graphs
• Spectral extrema of graphs: forbidden hexagon
• The spectral radius of graphs without paths and cycles of specified length

This page was built for publication: A spectral condition for odd cycles in graphs

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