On co-edge-regular graphs with 4 distinct eigenvalues

2025/03/15 by Ge, Hong-Jun, Koolen, Jack H.
#Combinatorics (math.CO) #FOS: Mathematics #Primary: 05C50 #Secondary: 05B15

paper · doi:10.48550/arxiv.2503.12025

Abstract

Tan et al. conjectured that connected co-edge-regular graphs with four distinct eigenvalues and fixed smallest eigenvalue, when having sufficiently large valency, belong to two different families of graphs. In this paper we construct two new infinite families of connected co-edge-regular graphs with four distinct eigenvalues and fixed smallest eigenvalue, thereby disproving their conjecture. Moreover, one of these constructions demonstrates that clique-extensions of Latin Square graphs are not determined by their spectrum.

Related

• A spectral characterization of the s-clique extension of the triangular graphs
• Recent progress on graphs with fixed smallest eigenvalue
• A note on graphs with exactly two main eigenvalues
• Some regular signed graphs with only two distinct eigenvalues
• On the minimum number of distinct eigenvalues of triangle-free strongly regular graphs