Non-isomorphic $d$-integral circulant graphs

Abstract

The algebraic degree $Deg(G)$ of a graph $G$ is the dimension of the splitting field of the adjacency polynomial of $G$ over the field $\mathbb{Q}$. It can be shown that for every positive integer $d$, there exists a circulant graph with algebraic degree $d$. Let $C(d)$ be the least positive integer such that there exists a circulant graph of order $C(d)$ having algebraic degree $d$. A graph $G$ is called $d$-integral if $Deg(G)=d$. We call a $d$-integral circulant graph \textit{minimal} if order of that graph equals $C(d)$. Let ${\mathcal{F}}_{n,d}$ denote the collection of isomorphism classes of connected, $d$-integral circulant graphs of some given possible order $n$. In this paper we compute the exact value of $C(d)$ and provide some bounds on $|{\mathcal{F}}_{n,d}|$, thereby showing that the minimal $d$-integral circulant graph is not unique. Moreover, we find the exact value of $|{\mathcal{F}}_{p,d}|$ where both $p$ and $d$ are prime.

19 pages, 1 table