Back to Search
Start Over
Eigenvalue multiplicity in triangle-free graphs
- 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.
- Subjects :
- Bipartite graph
Discrete mathematics
Numerical Analysis
Strongly regular graph
Algebra and Number Theory
Eigenvalue
010102 general mathematics
Eigenvalue multiplicity
Multiplicity (mathematics)
010103 numerical & computational mathematics
01 natural sciences
Star complement
Graph
Combinatorics
Triangle-free graph
Discrete Mathematics and Combinatorics
Bound graph
Geometry and Topology
0101 mathematics
Eigenvalues and eigenvectors
Mathematics
Subjects
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