The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters

2017/09/26 by Brouwer, Andries E., Cioabă, Sebastian M., Ihringer, Ferdinand +1 · 4 citations
#05C50 #05E30 #33C47 #33D45 #68R10 #90C47 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1709.09011

Abstract

We prove a conjecture by Van Dam and Sotirov on the smallest eigenvalue of (distance-j) Hamming graphs and a conjecture by Karloff on the smallest eigenvalue of (distance-j) Johnson graphs. More generally, we study the smallest eigenvalue and the second largest eigenvalue in absolute value of the graphs of the relations of classical P- and Q-polynomial association schemes.

Cited by

• Quantum Chromatic Number of Subgraphs of Orthogonality Graphs and the Distance-2 Hamming Graph
• On the quantum chromatic number of Hamming and generalized Hadamard graphs
• Spectral gap of G(n, αn, α² n) graphs and the giant component theorem
• Comparison of Hyperplane Rounding for Max-Cut and Quantum Approximate Optimization Algorithm over Certain Regular Graph Families

Related

• Minimum number of distinct eigenvalues of distance-regular and signed Johnson graphs
• The distance-regular graphs such that all of its second largest local eigenvalues are at most one
• Recent progress on graphs with fixed smallest eigenvalue
• Non-bipartite distance-regular graphs with a small smallest eigenvalue
• Distance-regular graphs with valency k having smallest eigenvalue at most -k/2