Non-isomorphic d-integral circulant graphs

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 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 minimal if order of that graph equals $C(d)$. Let Fn,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 |Fn,d|, thereby showing that the minimal d-integral circulant graph is not unique. Moreover, we find the exact value of |Fp,d| where both p and d are prime.