On Cayley representations of finite graphs over abelian p-groups

DOI10.1090/SPMJ/1639zbMATH Open1455.05051arXiv1903.00407OpenAlexW3119840764MaRDI QIDQ5144091FDOQ5144091

Authors:

Publication date: 14 January 2021

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

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.

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

Recommendations

• Recognizing and testing isomorphism of Cayley graphs over an abelian group of order \(4p\) in polynomial time
• Publication:2753924
• 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

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)

Cites Work

• Title not available (Why is that?)
• Isomorphism problem for a class of point-symmetric structures
• Permutation group approach to association schemes
• A solution of the isomorphism problem for circulant graphs
• On the isomorphism problem for cyclic combinatorial objects
• 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
• Title not available (Why is that?)
• Schurity of S-rings over a cyclic group and generalized wreath product of permutation groups.
• On Schur 2-groups
• On Schur \(p\)-groups of odd order
• Separability of Schur rings over abelian \(p\)-groups
• A family of permutation groups with exponentially many nonconjugated regular elementary abelian subgroups

Cited In (7)

• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• G-GRAPHS AND SPECIAL REPRESENTATIONS FOR BINARY DIHEDRAL GROUPS IN GL(2,ℂ)
• The Cayley isomorphism property for the group \(C_4\times C_p^2\)
• 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
• Representing Groups on Graphs
• Title not available (Why is that?)

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)