Hamiltonian decomposition of recursive circulant graphs (Q1972132): Difference between revisions

The graph \(G(N, d)\) has vertex set \(V=\{0,1,\dots,N-1\}\), with \(\{v,w\}\) an edge if \(v - w \equiv \pm d^i\) (mod \(N\)) for some \(i\) with \(0 \leq i \leq \lceil \log_dN \rceil - 1\). It is shown that the circulant graph \(G(cd^m,d)\) is Hamilton decomposable for all positive integers \(c, d\), and \(m\) with \(c<d\). This extends the work of \textit{C. Micheneau} [Disjoint Hamiltonian cycles in recursive circulant graphs, Inform. Process. Lett. 61, No. 5, 259-264 (1997)] and answers a special case of a question of \textit{B. Alspach} [Research problem 59, Discrete Math. 50, 115 (1984)].