Article
Details
Citation
Rowlinson P (2016) Eigenvalue multiplicity in triangle-free graphs. Linear Algebra and Its Applications, 493, pp. 484-493. https://doi.org/10.1016/j.laa.2015.12.012
Abstract
Let G be a connected triangle-free graph of order n>5 with μ∉{−1,0} as an eigenvalue of multiplicity k>1. We show that if d is the maximum degree in G then k≤n−d−1; moreover, if k=n−d−1 then either (a) G is non-bipartite and k≤(μ2+3μ+1)(μ2+2μ−1), with equality only if G is strongly regular, or (b) G is bipartite and k≤d−1, with equality only if G is a bipolar cone. In each case we discuss the extremal graphs that arise.
Keywords
Bipartite graph; Eigenvalue; Star complement; Strongly regular graph; Triangle-free graph
Journal
Linear Algebra and Its Applications: Volume 493
Status | Published |
---|---|
Publication date | 15/03/2016 |
Publication date online | 29/12/2015 |
Date accepted by journal | 10/12/2015 |
URL | http://hdl.handle.net/1893/23031 |
Publisher | Elsevier |
ISSN | 0024-3795 |
People (1)
Emeritus Professor, Mathematics