A solution of the isomorphism problem for circulant graphs

DOI10.1112/S0024611503014412MaRDI QIDQ4460731zbMATH OpenWikidataFDO

Authors Mikhail Muzychuk

Publication date 29 March 2004

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/S0024611503014412

zbMATH Keywords

circulant graphisomorphismsolving set

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• The isomorphism problem for circulant graphs via Schur ring theory
• On isomorphisms of circulant digraphs of bounded degree
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Isomorphisms of circulant digraphs
• Isomorphism testing for circulant graphs C_n (a, b)

Cited in

(77)

• One-matching bi-Cayley graphs over Abelian groups
• Permutation group approach to association schemes
• Schur rings.
• Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
• Recognizing circulant graphs of prime order in polynomial time
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
• Separability of Schur rings over abelian p-groups
• Isomorphisms of circulant digraphs
• Isomorphisms of circulant digraphs of degree 3
• The number of spanning trees in circulant graphs, its arithmetic properties and asymptotic
• Testing isomorphism of circulant objects in polynomial time
• On WL-rank and WL-dimension of some Deza circulant graphs
• Splitting fields of spectra of circulant graphs
• On automorphisms of the double cover of a circulant graph
• Greedy routing in circulant networks
• Eigenvalues of Cayley graphs
• Structural properties of Toeplitz graphs
• Four-dimensional almost Einstein manifolds with skew-circulant stuctures
• On the extendability of certain semi-Cayley graphs of finite Abelian groups
• Graphical representations of cyclic permutation groups
• Isomorphism between circulants and Cartesian products of cycles
• Curvature properties of 4-dimensional Riemannian manifolds with a circulant structure
• Cubic bi-Cayley graphs over abelian groups
• Graphs whose complement and square are isomorphic
• Schur rings over a product of Galois rings
• Testing set proportionality and the Ádám isomorphism of circulant graphs
• New families of circulant graphs without Cayley isomorphism property with r_i = 2
• The isomorphism problem for circulant graphs via Schur ring theory
• On isomorphisms of vertex-transitive graphs
• Isomorphism testing for circulant graphs C_n (a, b)
• The Laplacian and signless Laplacian spectrum of semi-Cayley graphs over abelian groups
• Optimal (v, 4, 2, 1) optical orthogonal codes with small parameters
• From Schur rings to constructive and analytical enumeration of circulant graphs with prime-cubed number of vertices
• Circulant graphs: efficient recognizing and isomorphism testing
• Design and serial construction of digraph braids
• ON ISOMORPHISMS OF VERTEX-TRANSITIVE CUBIC GRAPHS
• scientific article; zbMATH DE number 4135988 (Why is no real title available?)
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Automorphisms of endomorphism semigroups of reflexive digraphs
• Clique complexes and graph powers
• All normalized anti-monotonic overlap graph measures are bounded
• Isomorphism Problem for Metacirculant Graphs of Order a Product of Distinct Primes
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• scientific article; zbMATH DE number 867690 (Why is no real title available?)
• On isomorphism between circulant and Cartesian product of 2 cycles
• Recognizing generalized Sierpiński graphs
• Monomial isomorphisms of cyclic codes
• Two families of graphs that are Cayley on nonisomorphic groups
• Cayley graphs of more than one abelian group
• scientific article; zbMATH DE number 7559375 (Why is no real title available?)
• Generalized dihedral CI-groups
• On Cayley representations of finite graphs over abelian p-groups
• Powers of cycles, powers of paths, and distance graphs
• On Hamiltonian paths in distance graphs
• The Travelling Salesman Problem in symmetric circulant matrices with two stripes
• Implementing quantum Fourier transform using three qubits
• Recognizing circulant graphs in polynomial time: An application of association schemes
• Cyclic coverings of graphs. Counting rooted spanning forests and trees, Kirchhoff index, and Jacobians
• Canonization of a random circulant graph by counting walks
• Combinatorial refinement on circulant graphs
• Testing isomorphism of circulant objects in polynomial time
• The Kirchhoff indices for circulant graphs
• Stability of Cayley graphs and Schur rings
• Weakly distance-regular circulants. I
• Hamiltonicity in directed Toeplitz graphs T_n 1, 3, 6; t
• Cyclic m-DCI-groups and m-CI-groups
• Long cycles and paths in distance graphs
• Finding a cycle base of a permutation group in polynomial time
• On the BCI problem
• A lower bound for the Weisfeiler-Leman dimension of circulant graphs
• Classification of optimal \((v, 4, 1)\) binary cyclically permutable constant-weight codes and cyclic \(2\)-\((v, 4, 1)\) designs with \(v \leq 76\).
• Constructions of isospectral circulant graphs
• Further restrictions on the structure of finite DCI-groups: an addendum
• The isomorphism problem for abelian projective planes
• The spectrum of semi-Cayley graphs over abelian groups
• Schur rings over a Galois ring of odd characteristic
• On isomorphisms of circulant digraphs of bounded degree

This page was built for publication: A solution of the isomorphism problem for circulant graphs

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