Hamiltonian decomposition of recursive circulant graphs
type: Item
instance of: scholarly article
title: Hamiltonian decomposition of recursive circulant graphs
zbMATH Open document ID: 0944.05064
DOI: 10.1016/S0012-365X(99)00199-5
author: Daniel K. Biss
published in: Discrete Mathematics
publication date: 2000-09-15T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1423734
zbMATH Keywords: circulant graph
zbMATH Keywords: hamiltonian decomposable graphs
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00199-5
OpenAlex ID: W2056896777
description: scientific article; zbMATH DE number 1423734