Isomorphism testing for circulant graphs C n(a, b) - Nicoloso, Sara; Pietropaoli, Ugo (Utilitas Mathematica, 2012)
In this paper we focus on connected directed/undirected circulant graphs C n(a,b). We investigate some topological characteristics, and define a simple combinatorial model, which is new for the topic. Building on such a model, we derive a necessary and sufficient condition to test whether two circulant graphs C n(α,b) and C n(a',b') are isomorphic or not. The method is entirely elementary and consists of comparing two suitably computed integers in 1,.....n/gcd(n,a) gcd(n,b) - 1, and of verifying if gcd(n,a),gcd(n,6) = gcd(n, a'),gcd(n, b'), It also allows for building the mapping function in linear time. In addition, properties of the classes of mutually isomorphic graphs are analyzed.