Structural properties and formulae of the spectra of integral circulant graphs
Volume 184 / 2018
Abstract
Every integral circulant graph on $n$ vertices is isomorphic to some graph $\newcommand{\Icg}[2]{\mathrm{ICG}({#2},{#1})}\Icg{\mathcal D}{n}$ having vertex set $\mathbb{Z}/n\mathbb{Z}$ and edge set \[ \{(a,b):\, a,b\in\mathbb{Z}/n\mathbb{Z} ,\, \gcd(a-b,n)\in {\cal D}\} \] for a uniquely determined set $\mathcal D$ of positive divisors of $n$. According to a conjecture of So, two integral circulant graphs are isomorphic if and only if their spectra, i.e. the eigenvalues of their adjacency matrices, coincide. In order to facilitate a deeper understanding of the interrelation between integral circulant graphs and their spectra, we deduce several structural spectral properties of $\newcommand{\Icg}[2]{\mathrm{ICG}({#2},{#1})}\Icg{\mathcal D}{p^k}$ with prime power order $p^k$ and establish an explicit parameterisation of the spectrum of $\newcommand{\Icg}[2]{\mathrm{ICG}({#2},{#1})}\Icg{\mathcal D}{n}$ for multiplicative divisor sets $\mathcal D$. Our crucial tool will be the new concept of the leaping set of $\mathcal D$.
