The graphs for which the maximum multiplicity of an eigenvalue is two |
| |
Authors: | Charles R Johnson Paul Anthony Smith |
| |
Institution: | 1. Department of Mathematics , College of William and Mary , Williamsburg, VA, USA;2. Mathematics Department , UCLA , Los Angeles, CA, USA |
| |
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 composed of certain identified families of ‘exceptional’ partial 2-trees that are not linear. |
| |
Keywords: | graph partial 2-tree linear partial 2-tree exceptional partial 2-tree eigenvalue minimum rank of a graph |
|
|