Mutually Independent Hamiltonian Cycles of Cn x Cn

Authors: Kai-Siou Wu, Justie Su-Tzu Juan

Abstract:

In a graph G, a cycle is Hamiltonian cycle if it contain all vertices of G. Two Hamiltonian cycles C_1 = ⟨u_0, u_1, u_2, ..., u_{n−1}, u_0⟩ and C_2 = ⟨v_0, v_1, v_2, ..., v_{n−1}, v_0⟩ in G are independent if u_0 = v_0, u_i = ̸ v_i for all 1 ≤ i ≤ n−1. In G, a set of Hamiltonian cycles C = {C_1, C_2, ..., C_k} is mutually independent if any two Hamiltonian cycles of C are independent. The mutually independent Hamiltonicity IHC(G), = k means there exist a maximum integer k such that there exists k-mutually independent Hamiltonian cycles start from any vertex of G. In this paper, we prove that IHC(C_n × C_n) = 4, for n ≥ 3.

Keywords: Hamiltonian, independent, cycle, Cartesian product, mutually independent Hamiltonicity

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

References:

[1] F T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.
[2] J. M. Xu, Topological Structure and Analysis of Interconnection Net¬works. Kluwer Academic, 2001.
[3] J. M. Xu and M. Ma, "Survey on path and cycle embedding in some networks," Frontiers of Mathematics in China, vol. 4, no. 2, pp. 217-252, jun 2007.
[4] S. G. Aid, Parallel computation: models and methods. Prentice Hall, 1997.
[5] G. Chartrand and 0. R. Oellermann., Applied and algorithmic graph theory. McGraw-Hill, 1993.
[6] Y. L. Lai, D. C. Yu, and L. H. Hsu, "Mutually independent hamiltonian cycle of burnt pancake graphs," IEICE-Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E94A, no. 7, pp. 1553-1557, Jul 2011.
[7] Y. K Shih, H. C. Chuang, S. S. Kao, and J. J. M. Tan, "Mutually inde-pendent hamiltonian cycles in dual-cubes," Journal of Supercomputing, vol. 54, no. 2, pp. 239-251, Nov 2010.
[8] 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, no. 3, pp. 319-331, May 2011.
[9] T. L. Kueng, T. Liang, and L. H. Hsu, "Mutually independent hamil-tonian cycles of binary wrapped butterfly graphs," Mathematical and Computer Modelling, vol. 48, no. 11-12, pp. 1814-1825, Dec 2008.
[10] S. Y.-P. Chang, J. S.-T. Juan, C.-K. Lin, J. J. M. Tan, and L.-H. Hsu, "Mutually independent hamiltonian connectivity of (n, k)-star graphs," Annals of Combinatorics, vol. 13, pp. 27-52, 2009.
[11] T. L. Kung, C. K Lin, T. Liang, J. J. M. Tan, and L. H. Hsu, "Fault-free mutually independent hamiltonian cycles of faulty star graphs," International Journal of Computer Mathematics, vol. 88, no. 4, pp. 731¬746, 2011.
[12] C.-D. Lin, "Mutually independent hamiltonian cycles on arrangement graphs," Master's thesis, Chung Yuan Christian University, 2011.
[13] C. M. Sun, C. K. Lin, H. M. Huang, and L. H. Hsu, "Mutually independent hamiltonian cycles in hypercubes," in Parallel Architec-tures,Algorithms and Networks, 2005. ISPAN 2005. Proceedings. 8th International Symposium on, 2005, p. 6.
[14] S. Y. Hsieh and P. Y. Yu, "Fault-free mutually independent hamiltonian cycles in hypercubes with faulty edges," Journal of Combinatorial Optimization, vol. 13, no. 2, pp. 153-162, Feb 2007.
[15] C. K. Lin, J. J. M. Tan, H. M. Huang, D. F. Hsu, and L. H. Hsu, "Mutually independent hamiltonian cycles for the pancake graphs and the star graphs," Discrete Mathematics, vol. 309, no. 17, pp. 5474-5483, 2009.
[16] K. W. Tang and S. A. Padubidri, "Diagonal and toroidal mesh networks," Computers, IEEE Transactions on, vol. 43, no. 7, pp. 815-826, 1994.