On regular graphs with four distinct eigenvalues

Abstract

Let $\mathcal{G}(4,2)$ be the set of connected regular graphs with four distinct eigenvalues in which exactly two eigenvalues are simple, $\mathcal{G}(4,2,-1)$ (resp. $\mathcal{G}(4,2,0)$) the set of graphs belonging to $\mathcal{G}(4,2)$ with $-1$ (resp. $0$) as an eigenvalue, and $\mathcal{G}(4,\ge -1)$ the set of connected regular graphs with four distinct eigenvalues and second least eigenvalue not less than $-1$. In this paper, we prove the non-existence of connected graphs having four distinct eigenvalues in which at least three eigenvalues are simple, and determine all the graphs in $\mathcal{G}(4,2,-1)$. As a by-product of this work, we characterize all the graphs belonging to $\mathcal{G}(4,\ge -1)$ and $\mathcal{G}(4,2,0)$, respectively, and show that all these graphs are determined by their spectra.

13 pages, 1 figure

References in corpus (2)

• Biregular graphs with three eigenvalues
• Graphs with many valencies and few eigenvalues

Cited by in corpus (4)

• Monotonic normalized heat diffusion for regular bipartite graphs with four eigenvalues
• Two characterizations of the grid graphs
• A spectral characterization of the s-clique extension of the square grid graphs
• The full chracterazation of the graphs with a L-eigenvalue of multiplicity $n-3$