Isomorphisms, Symmetry and Computations in Algebraic Graph Theory

2017/06/19 by Gareth A. Jones, Roman Nedela, Ilia Ponomarenko +1 · 11 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algebra over a field #Algebraic graph theory #Algebraic number #Algorithm #Computation #Computer science #Discrete mathematics #Geometry #Graph #Graph Theory and Algorithms #Mathematical analysis #Mathematics #Pure mathematics #Symmetry (geometry) #cs.DM #math.CO #msc:05C85 #msc:05E18

paper · pdf · doi:10.1007/978-3-030-32808-5

published in Springer proceedings in mathematics & statistics (Springer International Publishing) · 22 pages

arxiv created 2017/06/19 · openalex created_date 2017/06/30 · openalex publication_date 2020/01/01 · arxiv updated 2021/07/06 · openalex updated_date 2026/08/05

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₂× C₂× 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.

Citations

• Canonical labeling of graphs
• An Enumeration of the Supercharacter Theories of C_p × C₂ × C₂ for Prime p