Isomorphisms, Symmetry and Computations in Algebraic Graph Theory

Autor:	Roman Nedela, Ilia Ponomarenko
Rok vydání:	2020
Předmět:	Combinatorics Discrete mathematics Cayley's theorem Cayley graph Cayley table Cayley transform Elementary abelian group Graph isomorphism Abelian group Rank of an abelian group Mathematics
Zdroj:	Springer Proceedings in Mathematics & Statistics ISBN: 9783030328078
DOI:	10.1007/978-3-030-32808-5
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e747ecded7fc7e4938738503c04a5e89 https://doi.org/10.1007/978-3-030-32808-5 Zobrazit plný text záznamu