Eigenvalue multiplicity in regular graphs

Citation

Rowlinson P (2019) Eigenvalue multiplicity in regular graphs. Discrete Applied Mathematics, 269, pp. 11-17. https://doi.org/10.1016/j.dam.2018.07.023

Abstract
Let G be a connected r-regular graph of order n with µ as an eigenvalue of multiplicity k, where r > 2 and µ ≠ -1,0 . We show that k / n ≤ (r - 1) / (r + 1),, with equality if only if r = 3, µ = 1 and G and is the Petersen graph. We observe that whenever r > 2 there exists an r-regular graph with an eigenvalue µ ≠ -1,0 for which k / n > (r - 2) / (r + 2). Lastly we find an improved upper bound for k when r > 3 and G has a tree as a star complement for µ.

Keywords
Eigenvalue; Regular graph; Star complement

Journal
Discrete Applied Mathematics: Volume 269