Recognizing Recursive Circulant Graphs (Extended Abstract)

Recursive circulant graphs G(N,d) have been introduced in 1994 by Park and Chwa [PC94] as a new topology for interconnection networks. Recursive circulant graphs G(N, d) are circulant graphs with N nodes and with jumps of powers of d. A subfamily of recursive circulant graphs (more precisely, G(2k, 4)) is of same order and degree than the hypercube of dimension k, with sometimes better parameters, such as diameter [PC94, GMR98]. Embeddings among recursive circulant graphs, hypercubes and Knodel graphs of order 2k have also been studied in [PC, FR98b]. Here, following a question raised in [CFG99], we give, thanks to a sharp structural analysis of such graphs, an O(cdm+2 · (2m)d) algorithm to determine if a given graph is a recursive circulant graph of the form G(cdm,d), for any d ≥ 3, except in the case where c is even while d is odd. Notably, in the case where d = O(1), this gives an O(N·(log(N))O(1)) algorithm, with N = cdm. Moreover, applying this algorithm to recursive circulant graphs G(2k,4) gives us an O(1k · k4) recognition algorithm for such graphs.