The Graphs for which the Maximum Multiplicity of an Eigenvalue is Two

2007/01/20 by Charles R. Johnson, Johnson, Charles R., Raphael Loewy +3 · 2 citations
Computer Science · Mathematics · #05C50 #15A57 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.math/0701562

openalex publication_date 2007/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Characterized are all simple undirected graphs G such that any real symmetric matrix that has graph G has no eigenvalues of multiplicity more than 2. All such graphs are partial 2-trees (and this follows from a result for rather general fields), but only certain partial 2-trees guarantee maximum multiplicity 2. Among partial linear 2-trees, they are only those whose vertices can be covered by two "parallel" induced paths. The remaining graphs that guarantee maximum multiplicity 2 are comprised by certain identified families of "exceptional" partial 2-trees that are not linear.

Cited by

• Multiplicity Bounds for Arbitrary Eigenvalues of Connected Signed Graphs
• The Classification of Graphs on 8 vertices with Coinciding Zero Forcing number and Maximum Nullity

Related

• A characterization on trees T with m(T, λ)=p(T)-2
• The graphs with all but two eigenvalues equal to ± 1
• The maximum multiplicity of an eigenvalue of symmetric matrices with a given graph
• The graphs with all but two eigenvalues equal to -2 or 0
• Achievable multiplicity partitions in the inverse eigenvalue problem of a graph