The graphs for which the maximum multiplicity of an eigenvalue is two

By Charles R. Johnson, Raphael Loewy, Paul Smith. 2007

60 citations recorded by the source corpus.

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 composed of certain identified families of ‘exceptional’ partial 2-trees that are not linear.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/8f46b3e10364fd81158fe30eedc374e2bc64af0f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Fatemeh Alinaghipour
2. Bahman Ahmadi
3. Karen Meagher
4. Michael S. Cavers
5. Shaun M. Fallat
6. Shahla Nasserasr
7. Leslie Hogben

In Computer Networks and Communications

1. Shaun M. Fallat

In Geometry and Topology

1. Michael S. Cavers
2. Karen Meagher
3. Shaun M. Fallat
4. Leslie Hogben
5. Ali Ahmad
6. Thomas Zaslavsky

Citations in the corpus

• Minimum number of distinct eigenvalues of graphs (2013, methodology): “Using [15], our investigation reduces to testing, which graphs G either of two parallel paths or from the exceptional list given in [15], satisfy q(G) = |V (G)| − 1.”