Testing isomorphism of circulant objects in polynomial time

DOI10.1016/J.JCTA.2019.105128MaRDI QIDQ2010626zbMATH OpenOpenAlexFDO

Authors Mikhail Muzychuk, Ilya Ponomarenko

Publication date 27 November 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

graph isomorphism problemcirculant combinatorial object

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: Let $frakK$ be a class of combinatorial objects invariant with respect to a given regular cyclic group. It is proved that the isomorphism of any two objects $X,YinfrakK$ can be tested in polynomial time in sizes of $X$ and $Y$.

Recommendations

• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Finding a cycle base of a permutation group in polynomial time
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Isomorphism testing for circulant graphs \(C_n (a, b)\)
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time

Cites work

• scientific article; zbMATH DE number 894528 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)
• A polynomial bound for the orders of primitive solvable groups
• A solution of an equivalence problem for semisimple cyclic codes
• A solution of the isomorphism problem for circulant graphs
• A unifying method for the design of algorithms canonizing combinatorial objects
• Cyclic groups are CI-groups for balanced configurations
• Isomorphism of graphs which are pairwise k-separable
• Isomorphism problem for a class of point-symmetric structures
• Isomorphism problem for relational structures with a cyclic automorphism
• Isomorphisms of cyclic combinatorial objects
• Multipliers and generalized multipliers of cyclic objects and cyclic codes
• On the isomorphism problem for cyclic combinatorial objects
• On Ádám's conjecture for circulant graphs
• The Cayley isomorphism property for Cayley maps
• The equivalence of two cyclic objects on pq elements

Cited in

(9)

• Testing set proportionality and the Ádám isomorphism of circulant graphs
• Isomorphism testing for circulant graphs \(C_n (a, b)\)
• Finding a cycle base of a permutation group in polynomial time
• Combinatorial refinement on circulant graphs
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Testing isomorphism of circulant objects in polynomial time
• Polynomial time recognition and testing of isomorphism of cyclic tournaments
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Finding the automorphism group of a circulant association scheme in polynomial time

This page was built for publication: Testing isomorphism of circulant objects in polynomial time

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