Skip to Main Content

St. Petersburg Mathematical Journal

This journal is a cover-to-cover translation into English of Algebra i Analiz, published six times a year by the mathematics section of the Russian Academy of Sciences.

ISSN 1547-7371 (online) ISSN 1061-0022 (print)

The 2024 MCQ for St. Petersburg Mathematical Journal is 0.68.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On Cayley representations of finite graphs over Abelian $p$-groups
HTML articles powered by AMS MathViewer

by G. Ryabov
Translated by: The author
St. Petersburg Math. J. 32 (2021), 71-89
DOI: https://doi.org/10.1090/spmj/1639
Published electronically: January 11, 2021
PDF | Request permission

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.
References
  • B. Yu. Weisfeiler and A. A. Leman, Reduction of a graph to a canonical form and an algebra which appears in the process, NTI. Ser. 2. Inform. Anal.9 (1968), pp. 12–16. (Russian)
  • S. A. Evdokimov and I. N. Ponomarenko, Characterization of cyclotomic schemes and normal Schur rings over a cyclic group, Algebra i Analiz 14 (2002), no. 2, 11–55 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 14 (2003), no. 2, 189–221. MR 1925880
  • S. A. Evdokimov and I. N. Ponomarenko, Schurity of S-rings over a cyclic group and the generalized wreath product of permutation groups, Algebra i Analiz 24 (2012), no. 3, 84–127 (Russian, with Russian summary); English transl., St. Petersburg Math. J. 24 (2013), no. 3, 431–460. MR 3014128, DOI 10.1090/S1061-0022-2013-01246-5
  • M. Muzychuk and I. Ponomarenko, On Schur 2-groups, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 435 (2015), no. Voprosy Teorii Predstavleniĭ Algebr i Grupp. 28, 113–162 (Russian, with English summary); English transl., J. Math. Sci. (N.Y.) 219 (2016), no. 4, 565–594. MR 3493620, DOI 10.1007/s10958-016-3128-z
  • G. K. Ryabov, On the separability of Schur rings over abelian $p$-groups, Algebra Logika 57 (2018), no. 1, 73–101 (Russian); English transl., Algebra Logic 57 (2018), no. 1, 49–68. MR 3836508, DOI 10.1007/s10469-018-9478-5
  • L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad. Sci. Hungar. 29 (1977), no. 3-4, 329–336. MR 485447, DOI 10.1007/BF01895854
  • G. Chen and I. Ponomarenko, Lectures on coherent configurations (2019), http://www.pdmi.ras.ru/~inp/ccNOTES.pdf.
  • Sergei Evdokimov and Ilia Ponomarenko, Permutation group approach to association schemes, European J. Combin. 30 (2009), no. 6, 1456–1476. MR 2535396, DOI 10.1016/j.ejc.2008.11.005
  • S. Evdokimov, M. Muzychuk, and I. Ponomarenko, A family of permutation groups with exponentially many nonconjugated regular elementary abelian subgroups, Algebra i Analiz 29 (2017), no. 4, 45–52; English transl., St. Petersburg Math. J. 29 (2018), no. 4, 575–580. MR 3708863, DOI 10.1090/spmj/1507
  • M. Klin, C. Pech, and S. Reichard, COCO2P – a GAP package, 0.14, 07.02.2015, http://www.math.tu-dresden.de/~pech/COCO2P.
  • A. Hanaki and I. Miyamoto, Classification of association schemes with small number of vertices, http://math.shinshu-u.ac.jp/~hanaki/as/, 2016.
  • Mikhail Muzychuk, On the isomorphism problem for cyclic combinatorial objects, Discrete Math. 197/198 (1999), 589–606. 16th British Combinatorial Conference (London, 1997). MR 1674890
  • M. Muzychuk, A solution of the isomorphism problem for circulant graphs, Proc. London Math. Soc. (3) 88 (2004), no. 1, 1–41. MR 2018956, DOI 10.1112/S0024611503014412
  • R. Nedela and I. Ponomarenko, Recognizing and testing isomorphism of Cayley graphs over an abelian group of order $4p$ in polynomial time, arXiv:1706.06145 [math.CO], (2017), 1–22.
  • Grigory Ryabov, On Schur $p$-groups of odd order, J. Algebra Appl. 16 (2017), no. 3, 1750045, 29. MR 3626712, DOI 10.1142/S0219498817500451
  • Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
  • On construction and identification of graphs, Lecture Notes in Mathematics, Vol. 558, Springer-Verlag, Berlin-New York, 1976. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler; Edited by Boris Weisfeiler. MR 0543783
Similar Articles
  • Retrieve articles in St. Petersburg Mathematical Journal with MSC (2020): 05E30, 05C60, 20B35
  • Retrieve articles in all journals with MSC (2020): 05E30, 05C60, 20B35
Bibliographic Information
  • G. Ryabov
  • Affiliation: Sobolev Institute of Mathematics, Novosibirsk; Novosibirsk State University, Novosibirsk, Russia
  • Email: gric2ryabov@gmail.com
  • Received by editor(s): March 3, 2019
  • Published electronically: January 11, 2021
  • Additional Notes: The work was supported by the Russian Foundation for Basic Research (project 18-31-00051).
  • © Copyright 2021 American Mathematical Society
  • Journal: St. Petersburg Math. J. 32 (2021), 71-89
  • MSC (2020): Primary 05E30, 05C60, 20B35
  • DOI: https://doi.org/10.1090/spmj/1639
  • MathSciNet review: 4057878