An Improved Construction Method for MIHCs on Cycle Composition Networks

Authors: Hsun Su, Yuan-Kang Shih, Shin-Shin Kao

Abstract:

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.

Keywords: Hamiltonian cycle, k-ary n-cube, cycle composition networks, mutually independent.

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

References:

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