Circulant graphs: recognizing and isomorphism testing in polynomial time

DOI10.1090/S1061-0022-04-00833-7zbMath1061.05045OpenAlexW2055552194WikidataQ55982756 ScholiaQ55982756MaRDI QIDQ4675535

Sergei Evdokimov, Ilya Nikolaevich Ponomarenko

Publication date: 4 May 2005

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

Full work available at URL: https://doi.org/10.1090/s1061-0022-04-00833-7

zbMATH Keywords

Cayley graphpolynomial-time algorithmRegular cycle automorphism group

Mathematics Subject Classification ID

Geometric group theory (20F65) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items

A SURVEY ON UNDIRECTED CIRCULANT GRAPHS ⋮ Hamiltonian problems in directed graphs with simple row patterns ⋮ On the separability problem for circulant S-rings ⋮ A family of permutation groups with exponentially many nonconjugated regular elementary abelian subgroups ⋮ 3-connected reduction for regular graph covers ⋮ Bases of Schurian antisymmetric coherent configurations and an isomorphism test for Schurian tournaments ⋮ On the WL-dimension of circulant graphs of prime power order ⋮ On Cayley representations of central Cayley graphs over almost simple groups ⋮ Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians ⋮ Schur rings over a product of Galois rings ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ On Hamiltonian paths in distance graphs ⋮ Long cycles and paths in distance graphs ⋮ Schur rings over a Galois ring of odd characteristic ⋮ Separability of Schur rings over abelian \(p\)-groups ⋮ On WL-rank and WL-dimension of some Deza circulant graphs ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ The Weisfeiler-Leman algorithm and recognition of graph properties ⋮ Permutation group approach to association schemes ⋮ Schur rings. ⋮ Two-closures of supersolvable permutation groups in polynomial time ⋮ Unnamed Item

Cites Work

• A polynomial bound for the orders of primitive solvable groups
• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments
• On the isomorphism problem for cyclic combinatorial objects
• On a new high dimensional Weisfeiler-Lehman algorithm
• On the structure of basic sets of Schur rings over cyclic groups
• Recognizing circulant graphs of prime order in polynomial time
• Coherent configurations. I
• On isomorphisms of finite Cayley graphs---a survey
• Ádám's conjecture is true in the square-free case
• On Schur rings over cyclic groups. II
• Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
• Two inequalities for parameters of a cellular algebra
• Separability number and Schurity number of coherent configurations
• Some NP-Complete Problems Similar to Graph Isomorphism
• Recognizing circulant graphs in polynomial time: An application of association schemes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Circulant graphs: recognizing and isomorphism testing in polynomial time