An Improved Construction Method for MIHCs on Cycle Composition Networks

Many well-known interconnection networks, such as kary n-cubes, recursive circulant graphs, generalized recursive circulant graphs, circulant graphs and so on, are shown to belong to the family of cycle composition networks. Recently, various studies about mutually independent hamiltonian cycles, abbreviated as MIHC-s, on interconnection networks are published. In this paper, using an improved construction method, we obtain MIHC-s on cycle composition networks with a much weaker condition than the known result. In fact, we established the existence of MIHC-s in the cycle composition networks and the result is optimal in the sense that the number of MIHC-s we constructed is maximal.

• Hsun Su
• Yuan-Kang Shih
• Shin-Shin Kao

• Hamiltonian cycle
• k-ary n-cube
• cycle composition networks
• mutually independent.

[1] J. A. Bondy and U. S. R Murty, Graph Theory with Applications, North-
Holland, New York, 1980.
[2] Y.-C. Chen, L.-H. Hsu and Jimmy J. M. Tan, A recursively construction scheme for super fault-tolerant hamiltonian graphs, Applied Mathematics and Computation, Vol. 177, pp.465-481, 2006.
[3] Y.-C. Chen, Jimmy J. M. Tan, L.-H. Hsu and S.-S. Kao, Superconnectivity
and super-edge-connectivity for some interconnection networks, Applied Mathematice and Computation, Vol. 140, pp.245-254, 2003.
[4] T.-L. Kueng, C.-K. Lin, Tyne Liang, Jimmy J.M. Tan and L.-H. Hsu, Fault-tolerant hamiltonian connectedness of cycle composition networks,
Applied Mathematice and Computation, Vol. 196, pp.245-256, 2008.
[5] M.-F. Hsieh, H. Su, S.-S. Kao, L.-Y. Hsu, and Y.-K. Shih, Mutually
Independent Hamiltonian Cycles on Cycle Composition Networks, in
Proceeding of 2011 International Conference on Data Engineering and
Internet Technology (DEIT 2011), Bali, Indonesia, pp. 124-129.
[6] S.-Y. Hsieh, Fault-tolerant mutually independent Hamiltonian cycles
embedding on hypercubes, in Proceedings of the First International
Conference on Innovative Computing, Information and Control, 2, pp.
288-292, 2006.
[7] S.-Y. Hsieh and P.-Y. Yu, Fault-free Mutually Independent Hamiltonian
Cycles in Hypercubes with Faulty Edges, Journal of Combinatorial Optimization, Vol. 13, pp.153-162, 2007.
[8] Kao, S.-S. Wang, P.-H.: Mutually independent Hamiltonian cycles in
k-ary n-cubes when k is odd. In Proceedings of American Conference
on Applied Mathematics, Harvard University, Boston, USA, 116-121 (2009).
[9] C.-K. Lin, H.-M. Huang, L.-H. Hsu and S. Bau, Mutually Independent
Hamiltonian Paths in Star Networks, Networks, Vol. 46, pp.110-117, 2005.
[10] C.-K. Lin, Y.-K. Shih, Jimmy J. M. Tan, and L.-H. Hsu, Mutually
Independent Hamiltonian Cycles in Some Graphs, Ars Combinatoria, accepted.
[11] C.-K. Lin, Jimmy J. M. Tan, H.-M. Huang, D. Frank Hsu, and L.-H.
Hsu, Mutually Independent Hamiltonian Cycles for the Pancake Graphs
and the Star Graphs, Discrete Mathematics, Vol. 309, pp.5474-5483, 2009.
[12] Y.-K. Shih, H.-C. Chuang, S.-S. Kao and Jimmy J. M. Tan, Mutually
Independent Hamiltonian Cycles in dual-cubes, The Journal of Supercomputing,
Vol. 54, pp. 239-251, 2010.
[13] Y.-K. Shih, C.-K. Lin, D. Frank Hsu, Jimmy J. M. Tan, and L.-H.
Hsu, The Construction of Mutually Independent Hamiltonian Cycles in
Bubble-Sort Graphs, International Journal of Computer Mathematics,
Vol. 87, pp. 2212-2225, 2010.
[14] H. Su, J.-L. Pan and S.-S. Kao, Mutually Independent Hamiltonian Cycles in k-ary n-cubes when k is even, Computers and Electrical Engineering, Vol. 37, pp.319-331, 2011.
[15] C.-M. Sun, C.-K. Lin, H.-M. Huang and L.-H. Hsu, Mutually Independent
Hamiltonian Paths and Cycles in Hypercubes, Journal of
Interconnection Networks, Vol. 7, pp.235–255, 2006.
[16] S. A. Wong, Hamiltonian cycles and paths in butterfly graphs, Networks,
Vol. 26, pp.145-150, 1995.