A Hamiltonian Decomposition of 5-star

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.

• Walter Hussak
• Heiko Schröder

• interconnection networks
• paths and cycles
• graphs andgroups.

[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.