Recognizing and testing isomorphism of Cayley graphs over an abelian group of order $4p$ in polynomial time

Roman Nedela, Ilia Ponomarenko

Published 2017-06-19Version 1

We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2\times C_2\times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time.