|
This article is cited in 2 scientific papers (total in 2 papers)
Research Papers
On Cayley representations of finite graphs over Abelian $ p$-groups
G. K. Ryabovab a Novosibirsk State University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
Abstract:
A polynomial-time algorithm is constructed that, given a graph $ \Gamma $, finds the full set of nonequivalent Cayley representations of $ \Gamma $ over the group $ D\cong C_p\times C_{p^k}$, where $ p\in \{2,3\}$ and $ k\geq 1$. This result implies that the recognition and isomorphism problems for Cayley graphs over $ D$ can be solved in polynomial time.
Keywords:
coherent configurations, Cayley graphs, Cayley graph isomorphism problem.
Received: 03.03.2019
Citation:
G. K. Ryabov, “On Cayley representations of finite graphs over Abelian $ p$-groups”, Algebra i Analiz, 32:1 (2020), 94–120; St. Petersburg Math. J., 32:1 (2021), 71–89
Linking options:
https://www.mathnet.ru/eng/aa1684 https://www.mathnet.ru/eng/aa/v32/i1/p94
|
|