Back to Search Start Over

Eigenvalue multiplicity in triangle-free graphs

Authors :
Rowlinson, Peter
Source :
Linear Algebra and its Applications. 493:484-493
Publication Year :
2016
Publisher :
Elsevier BV, 2016.

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.

Details

ISSN :
00243795
Volume :
493
Database :
OpenAIRE
Journal :
Linear Algebra and its Applications
Accession number :
edsair.doi.dedup.....61dfaac9d77613ac0bfb648854e795ff
Full Text :
https://doi.org/10.1016/j.laa.2015.12.012