On the sum of the largest and smallest eigenvalues of odd-cycle free graphs

2025/07/23 by Abiad, Aida, Taranchuk, Vladislav, van Veluw, Thijs
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.17492

Abstract

Let G be a graph with adjacency eigenvalues λ₁ ≥ ⋯ ≥ λ_n. Both λ₁ + λ_n and the odd girth of G can be seen as measures of the bipartiteness of G. Csikvári proved in 2022 that for odd girth 5 graphs (triangle-free) it holds that (λ₁+λ_n)/n ≤ (3-2√ 2) < 0.1716. In this paper we extend Csikvári's result to general odd girth k proving that (λ₁+λ_n)/n = O(k^-1). In the case of odd girth 7, we prove a stronger upper bound of (λ₁+λ_n)/n < 0.0396.

Related

• On the sum of the largest and smallest eigenvalues of graphs with high odd girth
• Adjacency eigenvalues of graphs without short odd cycles
• Note on the sum of the smallest and largest eigenvalues of a triangle-free graph
• Girth and Laplacian eigenvalue distribution
• A solution to Erdős and Hajnal's odd cycle problem