Minimum number of distinct eigenvalues of distance-regular and signed Johnson graphs

2024/10/31 by Shaun Fallat, Himanshu Gupta, Fallat, Shaun +5 · 1 citation
Mathematics · Computer Science · #Graph theory and applications #Finite Group Theory Research #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2411.00250

Abstract

We study the minimum number of distinct eigenvalues over a collection of matrices associated with a graph. Lower bounds are derived based on the existence or non-existence of certain cycle(s) in a graph. A key result proves that every Johnson graph has a signed variant with exactly two distinct eigenvalues. We also explore applications to weighing matrices, linear ternary codes, tight frames, and compute the minimum rank of Johnson graphs. Further results involve the minimum number of distinct eigenvalues for graphs in association schemes, distance-regular graphs, and Hamming graphs. We also draw some connections with simplicial complexes and higher-order Laplacians.

Cited by

• The Smith normal form of Laplacian matrices of simplicial annuli and high dimensional trees

Related

• Minimum number of distinct eigenvalues of graphs
• Applications of analysis to the determination of the minimum number of distinct eigenvalues of a graph
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• The minimum number of distinct eigenvalues of a threshold graph is at most 4
• On the minimum number of distinct eigenvalues of triangle-free strongly regular graphs