TITLE:On Recognizing Cayley Graphs
AUTHORS:Lali Barrière, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans and John M. Robson
ABSTRACT:
Given a class C of Cayley graphs, and given an edge-colored
graph G of n vertices and m edges, we are
interested in the problem of checking whether there exists an
isomorphism $\phi$ preserving the colors such that G is
isomorphic by $\phi$ to a graph in C colored by the elements of
its generating set. In this paper, we give an O(m log
n)-time algorithm to check whether G is color-isomorphic
to a Cayley graph, improving a previous O(n4.752log
n) algorithm. In the case where C is the class of the
Cayley graphs defined on Abelian groups, we give an optimal
O(m)-time algorithm. This algorithm can be extended to check
color-isomorphism with Cayley graphs on Abelian groups of given
rank. Finally, we propose an optimal O(m)-time algorithm that
tests color-isomorphism between two Cayley graphs on
Zn, i.e., between two circulant graphs. This latter
algorithm is extended to an optimal O(n)-time algorithm that
tests color-isomorphism between two Abelian Cayley graphs of bounded
degree.