On the isomorphism problem for a family of cubic metacirculant graphs (Q1916397)

\((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.