Structural properties and formulae of the spectra of integral circulant graphs

J. W. Sander¹

¹ Institut für Mathematik und Angewandte Informatik Universität Hildesheim D-31141 Hildesheim, Germany

Acta Arithmetica, Tome 184 (2018) no. 3, pp. 297-315.

Résumé

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$.

Détail

DOI : 10.4064/aa171020-30-6

Keywords: every integral circulant graph vertices isomorphic graph newcommand icg mathrm icg icg mathcal having vertex set mathbb mathbb edge set mathbb mathbb gcd a b cal uniquely determined set mathcal positive divisors according conjecture integral circulant graphs isomorphic only their spectra eigenvalues their adjacency matrices coincide order facilitate deeper understanding interrelation between integral circulant graphs their spectra deduce several structural spectral properties newcommand icg mathrm icg icg mathcal prime power order establish explicit parameterisation spectrum newcommand icg mathrm icg icg mathcal multiplicative divisor sets nbsp mathcal crucial tool concept leaping set nbsp mathcal