Article
Details
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
Status | Published |
---|---|
Publication date | 30/09/2019 |
Publication date online | 20/09/2018 |
Date accepted by journal | 25/07/2018 |
ISSN | 0166-218X |
People (1)
Emeritus Professor, Mathematics