A Hamiltonian Decomposition of 5-star

Authors: Walter Hussak, Heiko Schröder

Abstract:

Star graphs are Cayley graphs of symmetric groups of permutations, with transpositions as the generating sets. A star graph is a preferred interconnection network topology to a hypercube for its ability to connect a greater number of nodes with lower degree. However, an attractive property of the hypercube is that it has a Hamiltonian decomposition, i.e. its edges can be partitioned into disjoint Hamiltonian cycles, and therefore a simple routing can be found in the case of an edge failure. The existence of Hamiltonian cycles in Cayley graphs has been known for some time. So far, there are no published results on the much stronger condition of the existence of Hamiltonian decompositions. In this paper, we give a construction of a Hamiltonian decomposition of the star graph 5-star of degree 4, by defining an automorphism for 5-star and a Hamiltonian cycle which is edge-disjoint with its image under the automorphism.

Keywords: interconnection networks, paths and cycles, graphs andgroups.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061444

References:

[1] S.B.Akers, D.Harel, and B.Krishnamurthy, "The star graph: an attractive alternative to the n-cube," Int. Conf. on Parallel Processing, Chicago, USA, 1987, 393-400.
[2] K.Okuda and S.W.Song, "Revisiting Hamiltonian decomposition of the hypercube," Proc. 13th Symp. on Integrated Circuits and Systems Design, Manaus, Brazil, 2000, 55-60.
[3] R.Rowley and B.Bose, "On the number of disjoint Hamiltonian cycles in De Bruijn Graphs," Oregon State University Technical Report 93-80-09, 1993.
[4] M.M.Bae and B.Bose, "Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes," IEEE Transactions on Computers, 52(10), 2003, 1271- 1284.
[5] R.Cada, T.Kaiser, M.Rosenfeld, and Z.Ryjacek, "Disjoint Hamiltonian cycles in the star graph," Information Processing Letters, 110(1), 2009, 30-35.
[6] S.J.Curran, and J.A.Gallian, "Hamiltonian cycles and paths in Cayley graphs and digraphs - a survey," Discrete Mathematics, 156, 1996, 1-18.
[7] T.-K.Li, J.J.M.Tan, L.-H.Hsu, "Hyper Hamiltonian laceability on edge fault star graph," Information Sciences, 165, 2004, 59-71.
[8] J.-C.Bermond, O.Favaron, and M.Maheo, "Hamiltonian decomposition of Cayley graphs of degree 4," Journal of Combinatorial Theory, 46, 1989, 142-153.
[9] J.-H.Park, "Hamiltonian decomposition of recursive circulants," Proc. 9th Int. Symp. of Algorithms and Computation ISAAC-98, Taejon, Korea, 1998, 297-306.
[10] V.L.Kompel-makher, and V.A.Liskovets, "Sequential generation of arrangements by means of a basis of transpositions," Kibernetica, 3, 1975, 17-21.