On graphs with large third eigenvalue

2025/01/05 by Leonida, Giacomo, Li, Sida · 1 citation
#05C50 #15A42 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2501.02563

Abstract

Given a graph G, let λ₃ denote the third largest eigenvalue of its adjacency matrix. In this paper, we prove various results towards the conjecture that λ₃(G) ≤ (|V(G)|)/(3), motivated by a question of Nikiforov. We generalise the known constructions that yield λ₃(G) = (|V(G)|)/(3) - 1 and prove the inequality holds for G strongly regular, a regular line graph or a Cayley graph on an abelian group. We also consider the extended problem of minimising λ_n-1 on weighted graphs and reduce the existence of a minimiser with simple final eigenvalue to a vertex multiplication of a graph on 11 vertices. We prove that the minimal λ_n-1 over weighted graphs is at most O(√(n)) from the minimal λ_n-1 over unweighted graphs.

Cited by

• Graph Eigenvalues and Projection Constants

Related

• Strengthened upper bound on the third eigenvalue of graphs
• Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues
• Improved lower bounds on the extrema of eigenvalues of graphs
• On the sum of the largest A_α-eigenvalues of graphs
• Extrema of graph eigenvalues