On graphs with an eigenvalue of maximal multiplicity

Citation

Rowlinson P (2013) On graphs with an eigenvalue of maximal multiplicity. Discrete Mathematics, 313 (11), pp. 1162-1166. https://doi.org/10.1016/j.disc.2011.11.024

Abstract
Let G be a graph of order n with an eigenvalue μ≠-1,0 of multiplicity k<n-2. It is known that k≤n+√2-2n+¼, equivalently k≤½t(t-1), where t=n-k>2. The only known examples with k=½t(t-1) are 3K2 (with n=6, μ=1, k=3) and the maximal exceptional graph G36 (with n=36, μ=-2, k=28). We show that no other example can be constructed from a strongly regular graph in the same way as G36 is constructed from the line graph L(K9).

Keywords
Eigenvalue multiplicity; Strongly regular graph; Star set

Journal
Discrete Mathematics: Volume 313, Issue 11

• BoundVer4A.pdf