The Geometric Kernel of Integral Circulant Graphs

Abstract

By a suitable representation in the Euclidean plane, each circulant graph $G$, i.e. a graph with a circulant adjacency matrix ${\mathcal A}(G)$, reveals its rotational symmetry and, as the drawing's most notable feature, a central hole, the so-called \emph{geometric kernel} of $G$.

Every integral circulant graph $G$ on $n$ vertices, i.e. satisfying the additional property that all of the eigenvalues of ${\mathcal A}(G)$ are integral, is isomorphic to some graph $\mathrm{ICG}(n,\mathcal{D})$ 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 \mathcal{D}\}$ for a uniquely determined set $\mathcal{D}$ of positive divisors of $n$. A lot of recent research has revolved around the interrelation between graph-theoretical, algebraic and arithmetic properties of such graphs. In this article we examine arithmetic implications imposed on $n$ by a geometric feature, namely the size of the geometric kernel of $\mathrm{ICG}(n,\mathcal{D})$.