On Isospectral Integral Circulant Graphs

Abstract

Understanding when two non-isomorphic graphs can have the same spectra is a classic problem that is still not completely understood, even for integral circulant graphs. We say that a natural number $N$ satisfies the \emph{integral spectral Adàm property (ISAP)} if any two integral circulant graphs of order $N$ with the same spectra must be isomorphic. It seems to be open whether all $N$ satisfy the ISAP; Mönius and So showed that $N$ satisfies the ISAP if $N=p^k,p{q}^k,$ or $pqr$. We show that: (a) for any prime factorization structure $N=p_1^{a_1}\cdots p_k^{a_k}$, $N$ satisfies the ISAP for "most" values of the $p_i$; (b) $N=p^2{q}^n$ satisfy the ISAP if $p,q$ are odd and $(q-1)\nmid (p-1{)}^2(p+1)$; (c) all $N=p^2{q}^2$ satisfy the ISAP.