A spectral condition for odd cycles in graphs

By Vladimir Nikiforov. 2007

122 citations recorded by the source corpus.

Abstract Let G be a graph of sufficiently large order n , and let the largest eigenvalue μ ( G ) of its adjacency matrix satisfies μ ( G ) > ⌊ n 2 / 4 ⌋ . Then G contains a cycle of length t for every t ⩽ n / 320 This condition is sharp: the complete bipartite graph T 2 ( n ) with parts of size ⌊ n / 2 ⌋ and ⌈ n / 2 ⌉ contains no odd cycles and its largest eigenvalue is equal to ⌊ n 2 / 4 ⌋ . This condition is stable: if μ ( G ) is close to ⌊ n 2 / 4 ⌋ and G fails to contain a cycle of length t for some t ⩽ n / 321 , then G resembles T 2 ( n ) .

Subfields: Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/8df85bd59a7236b48811f7fe35653e3b387bbd87

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

Vladimir Nikiforov

In Geometry and Topology

Citations in the corpus

A survey on spectral conditions for some extremal graph problems (2021, unknown): “In 2008, Nikiforov [148] proved an analogue of the Bondy–Woodall Theorem 1.”
Some new results in extremal graph theory (2011, background): “This theorem, given in [79], is motivated by the following result of Bollobás ([6], p.”