A spectral condition for odd cycles in graphs

摘要

Let G be a graph of sufficiently large order n, and let the largest eigenvalue mu (G) of its adjacency matrix satisfies mu(G) > -root left perpendicular n(2)/4 right perpendicular. 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 left perpendicular n/2right perpendicular and inverted right perpendicular n/2 inverted left perpendicular contains no odd cycles and its largest eigenvalue is equal to root left perpendicular n(2)/4 right perpendicular. This condition is stable: if mu(G) is close to root left perpendicular n(2)/4 right perpendicular and G fails to contain a cycle of length t for some t <= n/321, then G resembles T-2(n). (c) 2007 Elsevier Inc. All rights reserved.