Isomorphisms of circulant digraphs (Q1804220): Difference between revisions

Let \(\mathbb{Z}_ n\) be the factor group \(\text{mod } n\) of the additive group of integers. The notion of circulant (directed) graph \(\text{DC}_ n(S)\) (on \(n\) vertices) is well known where \(S\) runs through the nonempty subsets of \(\mathbb{Z}_ n- \{0\}\). We write \(S_ 1\simeq S_ 2\) if \(S_ 2\) results from \(S_ 1\) via multiplication by \(r\pmod n\) where \(r\) is relatively prime to \(n\). The reviewer posed the problem whether the isomorphy of \(\text{DC}_ n(S_ 1)\) and \(\text{DC}_ n(S_ 2)\) implies \(S_ 1\simeq S_ 2\) (the converse is evident) [J. Comb. Theory 2, 393 (1967); see also \S\S3-4 in Acta Cybern. 3, 187-214 (1977; Zbl 0374.94037)]. In the present article some properties of minimal generating systems \(S^*\) of \(\mathbb{Z}_ n\) are discussed, the automorphism groups of the graphs \(\text{DC}_ n(S^*)\) are determined, and it is shown that \(\text{DC}_ n(S^*)\) and \(\text{DC}_ n(S)\) are isomorphic only if \(S^*\simeq S\).