On the spectral Ádám property for circulant graphs

Bernard Mans*, Francesco Pappalardi, Igor Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)309-329
Number of pages21
JournalDiscrete Mathematics
Volume254
Issue number1-3
Publication statusPublished - 10 Jun 2002

Fingerprint

Dive into the research topics of 'On the spectral Ádám property for circulant graphs'. Together they form a unique fingerprint.

Cite this