Research output

Article in Journal ()

Eigenvalue multiplicity in triangle-free graphs

Citation
Rowlinson P (2016) Eigenvalue multiplicity in triangle-free graphs, Linear Algebra and Its Applications, 493, pp. 484-493.

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

StatusPublished
AuthorsRowlinson Peter
Publication date15/03/2016
Publication date online29/12/2015
Date accepted by journal10/12/2015
PublisherElsevier
ISSN 0024-3795
LanguageEnglish

Journal
Linear Algebra and its Applications: Volume 493

© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal