Constructing cospectral graphs

Abstract

Some new constructions for families of cospectral graphs are derived, and some old ones are considerably generalized. One of our new constructions is sufficiently powerful to produce an estimated 72% of the 51039 graphs on 9 vertices which do not have unique spectrum. In fact, the number of graphs of order n without unique spectrum is believed to be at least αn3g-1 for some α>0, where gn is the number of graphs of order n and n ≥ 7. Show more