我要吃瓜

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