On the spectral Adam property for circulant graphs

We investigate a certain condition for isomorphism between circulant graphs (known as the Ádám property) in a stronger form by referring to isospectrality rather than to isomorphism of graphs. We describe a wide class of graphs for which the Ádám conjecture holds. We apply these results to establish an asymptotic formula for the number of non-isomorphic circulant graphs and connected circulant graphs. Circulant graphs arise in many applications including telecommunication networks, VLSI design and distributed computation and have been extensively studied in the literature. In the important case of double loops (particular circulant graphs of degree 4) we give a complete classification of all possible isospectral graphs. Our method is based on studying the graph spectra with the aid of some deep results of algebraic number theory.21 page(s