On the Automorphism Group of Integral Circulant Graphs

Milan Bašić, Aleksandar Ilić

Abstract


The integral circulant graph $X_n (D)$ has the vertex set $Z_n = \{0, 1,\ldots$, $n{-}1\}$ and vertices $a$ and $b$ are adjacent, if and only if $\gcd(a{-}b$, $n)\in D$, where $D = \{d_1,d_2, \ldots, d_k\}$ is a set of divisors of $n$. These graphs play an important role in modeling quantum spin networks supporting the perfect state transfer and also have applications in chemical graph theory. In this paper, we deal with the automorphism group of integral circulant graphs and investigate a problem proposed in [W. Klotz, T. Sander, Some properties of unitary Cayley graphs, Electr. J. Comb. 14 (2007), #R45]. We determine the size and the structure of the automorphism group of the unitary Cayley graph $X_n (1)$ and the disconnected graph $X_n (d)$. In addition, based on the generalized formula for the number of common neighbors and the wreath product, we completely characterize the automorphism groups $Aut (X_n (1, p))$ for $n$ being a square-free number and $p$ a prime dividing $n$, and $Aut (X_n (1, p^k))$ for $n$ being a prime power.


Full Text: PDF