Disjoint Hamiltonian cycles in recursive circulant graphs. (English) Zbl 1336.05081
Summary: We show in this paper that the circulant graph \(G(2^{m}, 4)\) is Hamiltonian decomposable, and propose a recursive construction method. This is a partial answer to a problem posed by B. Alspach in [“Problem 59”, Discrete Math. 50, 115 (1984; doi:10.1016/0012-365X(84)90041-4)].
MSC:
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Alspach, B., Problems, Discrete Math., 50, 115 (1984) |
| [2] | Berge, C., Graphs and Hypergraphs (1976), North-Holland: North-Holland Amsterdam · Zbl 0483.05029 |
| [3] | Barth, D.; Raspaud, A., Two disjoint Hamiltonian cycles in the butterfly graph, Inform. Process. Lett., 51, 175-179 (1994) · Zbl 0807.05047 |
| [4] | Bermond, J. C.; Favaron, O.; Maheo, M., Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory B, 46, 142-153 (1989) · Zbl 0618.05032 |
| [5] | Curran, S. J.; Gallian, J. A., Hamiltonian cycles and paths in Cayley graphs and digraphs — a survey (1994), Preprint |
| [6] | Leighton, F. T., Introduction to Parallel Algorithms and Architecture: arrays, trees, hypercubes (1992), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA · Zbl 0743.68007 |
| [7] | Liu, J., Hamiltonian decompositions of Cayley graphs on abelian groups, Discrete Math., 131, 163-171 (1994) · Zbl 0809.05058 |
| [8] | Park, J.-H.; Chwa, K.-Y., Recursive circulant: a new topology for multicomputer networks, (Proc. Internat. Symp. Parallel Architectures, Algorithms and Networks (ISPAN’94). Proc. Internat. Symp. Parallel Architectures, Algorithms and Networks (ISPAN’94), Japan (1994), IEEE Press: IEEE Press New York), 73-80 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
