Title

Trees with very few eigenvalues

Document Type

Article

Publication Date

1990

Publication Title

Journal of Graph Theory

Department

Mathematics and Computer Science

Abstract

The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create graphs having the fewest possible eigenvalues. This construction is best at creating trees, but will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large amounts of symmetry. A corollary allows us to determine the values and multiplicities of all the nonsimple eigenvalues of the constructed graph.

Volume

14

Issue

4

pp.

509-517

ISSN

0364-9024

Link to Full Text

Share

COinS