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 F₍, ₃ 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 |F₍, ₃|, thereby showing that the minimal d-integral circulant graph is not unique. Moreover, we find the exact value of |F₏, ₃| where both p and d are prime.