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

Abstract

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.

22 pages

References in corpus (1)

• An Enumeration of the Supercharacter Theories of $C_p\times C_2\times C_2$ for Prime $p$

Cited by in corpus (5)

• The EKR-module property of pseudo-Paley graphs of square order
• The group $C_p^4\times C_q$ is a DCI-group
• Separability of Schur rings over an abelian group of order 4p
• On Cayley representations of finite graphs over abelian p-groups
• The subspace structure of maximum cliques in pseudo-Paley graphs from unions of cyclotomic classes