Isomorphism testing for circulant graphs

Abstract

In this paper we focus on connected directed/undirected circulant graphs Cn(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 Cn(a, b) and Cn(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, b)} = {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.

Topics

5 Figures and Tables

Download Full PDF Version (Non-Commercial Use)