On the isomorphism problem for a family of cubic metacirculant graphs

DOI10.1016/0012-365X(94)00100-WMaRDI QIDQ1916397zbMATH OpenFDO

Authors Ngo Dac Tan

Publication date 11 September 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00100-W

zbMATH Keywords

algorithmautomorphism groupcirculant graphsgeneralized Petersen graphsisomorphism checkingmetacirculant graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

\((m,n)\)-metacirculant graphs were introduced by \textit{B. Alspach} and \textit{T. D. Parsons} [Can. J. Math. 34, 307-318 (1982; Zbl 0467.05032)] using a set of subsets \(S_0,S_1,\dots,S_\mu\) of \(Z_n\), where \(\mu=\lfloor m/2\rfloor\). The author of the present paper had characterized earlier the components of cubic \((m,n)\)-metacirculant graphs with \(S_0\neq\varnothing\). These are either circulant graphs or generalized Petersen graphs with certain specifications. Using this component-characterization, the author first presents an algorithm of complexity \(O(\log^3_2(mn))\) to determine these components. Let \(\phi(m,n)\) denote the family of these \((m,n)\)-metacirculant graphs and \(\Phi=\bigcup \phi(m,n)\). In the main part, the author presents an algorithm for isomorphism checking for graphs in \(\Phi\) with same time complexity \(O(\log^3_2(mn))\). This is done by imbedding \(\Phi\) in the bigger class \(\Psi\) of graphs whose components are either circulant graphs or generalized Petersen graphs with given specifications, and painstakingly checking for isomorphism conditions between these graphs.

Recommendations

• A characterization of some cubic \((m,n)\)-metacirculant graphs
• On cubic metacirculant graphs
• Isomorphism Problem for Metacirculant Graphs of Order a Product of Distinct Primes

Cites work

• A Construction for Vertex-Transitive Graphs
• scientific article; zbMATH DE number 3933107 (Why is no real title available?)
• scientific article; zbMATH DE number 3943850 (Why is no real title available?)
• scientific article; zbMATH DE number 3754731 (Why is no real title available?)
• scientific article; zbMATH DE number 3349883 (Why is no real title available?)
• On cubic metacirculant graphs

Cited in

(7)

• Connectedness of cubic metacirculant graphs
• A characterization of some cubic \((m,n)\)-metacirculant graphs
• On half-transitive metacirculant graphs of prime-power order
• Products of circulant graphs are metacirculant.
• Cubic (m,n)-metacirculant graphs which are not Cayley graphs
• Isomorphism Problem for Metacirculant Graphs of Order a Product of Distinct Primes
• Some results on the lexicographic product of vertex-transitive graphs

This page was built for publication: On the isomorphism problem for a family of cubic metacirculant graphs

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