On Cayley representations of finite graphs over abelian p-groups

DOI10.1090/SPMJ/1639MaRDI QIDQ5144091zbMATH OpenOpenAlexFDO

Authors

Publication date 14 January 2021

Published in St. Petersburg Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.00407

zbMATH Keywords

Cayley graphscoherent configurationsCayley graph isomorphism problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph representations (geometric and intersection representations, etc.) (05C62) Subgroups of symmetric groups (20B35) Group rings of finite groups and their modules (group-theoretic aspects) (20C05)

Abstract: We construct a polynomial-time algorithm which given a graph $Gamma$ finds the full set of non-equivalent Cayley representations of $Gamma$ over the group $Dcong{C}_{p}imes{C}_{p^k}$, where $pin2,3$ and $kgeq1$. This result implies that the recognition and the isomorphism problems for Cayley graphs over $D$ can be solved in polynomial time.

Recommendations

• Recognizing and testing isomorphism of Cayley graphs over an abelian group of order \(4p\) in polynomial time
• scientific article; zbMATH DE number 1670648
• On Cayley representations of central Cayley graphs over almost simple groups
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• Representing Groups on Graphs

Cites work

• scientific article; zbMATH DE number 2007658 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• A family of permutation groups with exponentially many nonconjugated regular elementary abelian subgroups
• A solution of the isomorphism problem for circulant graphs
• Isomorphism problem for a class of point-symmetric structures
• On Schur 2-groups
• On Schur \(p\)-groups of odd order
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the isomorphism problem for cyclic combinatorial objects
• Permutation group approach to association schemes
• Schurity of S-rings over a cyclic group and generalized wreath product of permutation groups.
• Separability of Schur rings over abelian \(p\)-groups

Cited in

(7)

• Representing Groups on Graphs
• The Cayley isomorphism property for the group \(C_4\times C_p^2\)
• scientific article; zbMATH DE number 4108807 (Why is no real title available?)
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• Recognizing and testing isomorphism of Cayley graphs over an abelian group of order \(4p\) in polynomial time
• On Cayley representations of central Cayley graphs over almost simple groups
• G-GRAPHS AND SPECIAL REPRESENTATIONS FOR BINARY DIHEDRAL GROUPS IN GL(2,ℂ)

Describes a project that uses

Uses Software

• COCO2P

This page was built for publication: On Cayley representations of finite graphs over abelian \(p\)-groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144091)