臺灣博碩士論文加值系統

在一個圖形(graph) G 中，一個迴圈(cycle) C = ⟨v0, v1, ..., vk, v0⟩，定義
為一個相鄰(adjacent) 的點所組成的序列，且對所有1 ≤ i < j ≤ k，vi ≠ vj。
而在G 中，一個迴圈若包含了圖形G 中所有的點，則稱此迴圈為漢米爾頓迴
圈(Hamiltonian cycle)。若圖形G 中存在漢米爾頓迴圈則稱此圖為漢米爾頓
圖(Hamiltonian graph)。G 中的兩個漢米爾頓迴圈C1 = ⟨u0, u1, u2, ..., un−1, u0⟩
及C2 = ⟨v0, v1, v2, ..., vn−1, v0⟩ 稱為獨立(independent) 則表示u0 = v0 且對所有
1 ≤ i ≤ n−1，ui ≠ vi。若稱G 中的一個漢米爾頓迴圈集合C = {C1,C2, ...,Ck}
為互相獨立(imutually independent) 的意思是，集合中任兩個漢米爾頓迴圈
皆為獨立。一個圖形G 中的互相獨立漢米爾頓數(imutually independent
Hamiltonianicity) 以IHC(G) = k 表示，其定義為max{k ∈ N| 從圖形中任意
一點u 作為起點，皆存在k 個互相獨立漢米爾頓迴圈}。兩圖形G 與H 的
卡式積(Cartesian product) 為一個新的圖形並以G × H 表示，其點集合為
V (G) × V (H)，此圖形中若兩點(u, v) 與(u′, v′) 相連必須滿足：(1) u = u′ 且
vv′ ∈ E(H)，或(2) v = v′ 且uu′ ∈ E(G)。
在本論文中，我們針對了圖形G = G1 × G2，討論其互相獨立漢米爾頓
數的性質，其中G1 及G2 為漢米爾頓圖。我們證明了在給定不同的條件下，
IHC(G1 × G2) ≥ IHC(G1) 或IHC(G1) + 2。此外，我們參考環方格(toroidal
mesh) 圖形的定義，其等價於兩個迴圈做卡式積的圖形Cm × Cn，其中m, n 分
別代表兩迴圈的長度。本論文中也證明了對任意兩個正整數m, n ≥ 3 而言，
IHC(Cm × Cn) = 4。

In a graph G, a cycle C = ⟨v0, v1, ..., vk, v0⟩ is defined as a sequence of
adjacent vertices and for all 0 ≤ i < j ≤ k, vi ≠ vj ; a cycle is called Hamiltonian
cycle if it contains all vertices of G. If there exists a Hamiltonian cycle in G, then
G is a Hamiltonian graph. Two Hamiltonian cycles C1 = ⟨u0, u1, u2, ..., un−1, u0⟩
and C2 = ⟨v0, v1, v2, ..., vn−1, v0⟩ are independent if u0 = v0, ui ≠ vi for all 1 ≤
i ≤ n − 1. A set of Hamiltonian cycles C = {C1,C2, ...,Ck} of G are mutually
independent if any two different Hamiltonian cycles of C are independent. The
mutually independent Hamiltonianicity of graph G, namely IHC(G) = k, is the
maximum integer k such that for any vertex u of G there exists k-mutually
independent Hamiltonian cycles starting at u. The Cartesian product of graphs
G and H, written by G×H, is the graph with vertex set V (G)×V (H) specified
by putting (u, v) adjacent to (u′, v′) if and only if (1) u = u′ and vv′ ∈ E(H), or
(2) v = v′ and uu′ ∈ E(G).
In this thesis, we study mutually independent Hamiltonianicity on G =
G1×G2, where G1 and G2 are Hamiltonian graphs. We prove that IHC(G1×G2) ≥
IHC(G1) or IHC(G1) + 2 when given some difference conditions. We refer to
toroidal mesh graph and define graph Cm × Cn, where m, n are lengths of cycles.
We show that IHC(Cm × Cn) = 4 for any positive integers m, n ≥ 3.

Contents
誌謝I
論文摘要II
Abstract III
Contents V
List of Figures VII
List of Tables X
1 Introduction 1
1.1 Basic Definitions and Movtivation . . . . . . . . . . . . . . . . . . 1
1.2 Preview This Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 The Lower Bound of IHC(G1×G2) for Two Hamiltonian Graphs
G1 and G2 5
2.1 IHC(G1 × G2) ≥ IHC(G1) . . . . . . . . . . . . . . . . . . . . . . 6
2.2 IHC(G1 × G2) ≥ IHC(G1) + 2 for |V (G2)| Is Odd . . . . . . . . . 13
2.3 IHC(G1 × G2) ≥ IHC(G1) + 2 for |V (G2)| Is Even . . . . . . . . . 18
3 Mutually Independent Hamiltonianicity of Cm × Cn 25
3.1 IHC(Cm × Cn) = 4, for m, n Both Are Odd . . . . . . . . . . . . . 28
3.1.1 IHC(Cm × Cn) = 4, for m = n Both Are Odd . . . . . . . 28
3.1.2 IHC(Cm × Cn) = 4, for m ̸= n Both Are Odd . . . . . . . 31
3.2 IHC(Cm × Cn) = 4, for One of m, n Is Odd, the Other Is Even . . 37
3.2.1 IHC(Cm × Cn) = 4, for One of m, n Is 3, the Other Is Even 38
3.2.2 IHC(Cm × Cn) = 4, for One of m, n Is 4, the Other Is Odd 51
3.2.3 IHC(Cm ×Cn) = 4, for One of m, n Is Odd ≥ 5, the Other
Is Even . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 IHC(Cm × Cn) = 4, for m, n Both Are Even . . . . . . . . . . . . 59
3.3.1 IHC(Cm × Cn) = 4, for m = n Both Are Even . . . . . . . 59
3.3.2 IHC(Cm × Cn) = 4, for One of m, n Is 4, the Other Is Even 66
3.3.3 IHC(Cm × Cn) = 4, for m, n Both Are Even ≥ 6 and m ̸= n 73
4 Conclusion and Future Works 78
4.1 Summary of the Results . . . . . . . . . . . . . . . . . . . . . . . 78
4.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
References 81

List of Figures
2.1 The constructions of two Hamiltonian cycles of G1 × C8 starting
at e0. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 An illustration of two Hamiltonian cycles of G1 × C7 starting at e0. 8
2.3 An illustration of two Hamiltonian cycles of G1 × C8 starting at e0. 8
2.4 The constructions of I1 Hamiltonian cycles of G1 × H starting at
e0, where m ≥ 4I1 − 1, n ≥ 2I1. . . . . . . . . . . . . . . . . . . . 11
2.5 An illustration of H1 and H4 for G1 × C8. . . . . . . . . . . . . . 11
2.6 An illustration of H2, H3 and H4 for G1 × C8. . . . . . . . . . . . 12
2.7 The constructions of (k + 1)th and (k + 2)th Hamiltonian cycles
of G1 × Cn starting at e0 for n is odd. . . . . . . . . . . . . . . . 15
2.8 An illustration of H1 and Hk+1 for G1 × C7. . . . . . . . . . . . . 15
2.9 An illustration of H1 and Hk+2 for G1 × C7. . . . . . . . . . . . . 16
2.10 An illustration of H2 and Hk+1 for G1 × C7. . . . . . . . . . . . . 16
2.11 An illustration of H2 and Hk+2 for G1 × C7. . . . . . . . . . . . . 16
2.12 An illustration of Hk+1 and Hk+2 for G1 × C7. . . . . . . . . . . . 17
2.13 The constructions of (k + 1)th and (k + 2)th Hamiltonian cycles
of G1 × Cn starting at e0 for n is even. . . . . . . . . . . . . . . . 20
2.14 An illustration of H1 and Hk+1 for G1 × C8. . . . . . . . . . . . . 21
2.15 An illustration of H1 and Hk+2 for G1 × C8. . . . . . . . . . . . . 21
2.16 An illustration of H2, H3 and Hk+1 for G1 × C8. . . . . . . . . . . 21
2.17 An illustration of H2, H3 and Hk+2 for G1 × C8. . . . . . . . . . . 22
2.18 An illustration of Hk+1 and Hk+2 for G1 × C8. . . . . . . . . . . . 22
3.1 C6 × C5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 The construction of four Hamiltonian cycles of Cn × Cn starting
at e for n is odd. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 4-mutually independent Hamiltonian cycles of C5 ×C5 starting at
(0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 The construction of four Hamiltonian cycles of C9×C5 starting at e. 34
3.5 4-mutually independent Hamiltonian cycles of C9 ×C5 starting at
(0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Four Hamiltonian cycles of C4 × C3 starting at (0, 0). . . . . . . . 40
3.7 Four Hamiltonian cycles of C6 × C3 starting at (0, 0). . . . . . . . 41
3.8 Four Hamiltonian cycles of C8 × C3 starting at (0, 0). . . . . . . . 42
3.9 Four Hamiltonian cycles of C10 × C3 starting at (0, 0). . . . . . . 42
3.10 Four Hamiltonian cycles of C12 × C3 starting at (0, 0). . . . . . . 45
3.11 Four Hamiltonian cycles of C14 × C3 starting at (0, 0). . . . . . . 47
3.12 The construction of four Hamiltonian cycles of Cm × C3 starting
at (0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.13 The construction of four Hamiltonian cycles of C16 × C3 starting
at e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.14 Four Hamiltonian cycles of C4 × C7 starting at (0, 0). . . . . . . . 53
3.15 The construction of four Hamiltonian cycles of C4 × Cn starting
at (0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.16 The construction of four Hamiltonian cycles of C4×C9 starting at e. 55
3.17 The construction of four Hamiltonian cycles of Cm × C5 starting
at (0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.18 The construction of four Hamiltonian cycles of C10 × C5 starting
at e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.19 The construction of four Hamiltonian cycles of Cn × Cn starting
at e for n is even. . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.20 4-mutually independent Hamiltonian cycles of C6 ×C6 starting at
(0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.21 Four Hamiltonian cycles of C6 × C4 starting at (0, 0). . . . . . . . 67
3.22 Four Hamiltonian cycles of C8 × C4 starting at (0, 0). . . . . . . . 68
3.23 The construction of four Hamiltonian cycles of Cm × C4 starting
at (0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.24 The construction of four Hamiltonian cycles of C12 × C4 starting
at e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.25 The construction of four Hamiltonian cycles of C10 × C4 starting
at e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.26 The construction of four Hamiltonian cycles of Cm × Cn starting
at (0, 0) for m, n both are even. . . . . . . . . . . . . . . . . . . . 75
3.27 The construction of four Hamiltonian cycles of C8×C6 starting at e. 75

List of Tables
3.1 An Illustration of Property 4 Where a = 1, b = −1, n − 1, 0 or 1 . 26
3.2 An Illustration of Property 5 Where a = 1, b = 1, 1 − n, 0 or −1 . 27
3.3 An Illustration of Four Hamiltonian Cycles in Case 1 for Proving
Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4 An Illustration of Four Hamiltonian Cycles in Case 1 for Proving
Theorem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 4-Mutually Independent Hamiltonian Cycles in C4 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 4-Mutually Independent Hamiltonian Cycles in C6 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.7 4-Mutually Independent Hamiltonian Cycles in C8 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.8 4-Mutually Independent Hamiltonian Cycles in C10 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.9 4-Mutually Independent Hamiltonian Cycles in C12 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.10 4-Mutually Independent Hamiltonian Cycles in C14 × C3 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.11 H2(t2) and H3(t2) for 7 ≤ t2 ≤ 15 in Case 2.2 for Proving Theorem 6 47
3.12 4-Mutually Independent Hamiltonian Cycles in C4 × C7 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.13 4-Mutually Independent Hamiltonian Cycles in C4 × C4 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.14 4-Mutually Independent Hamiltonian Cycles in C6 × C4 Starting
at (0, 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.15 4-Mutually Independent Hamiltonian Cycles in C8 × C4 Starting
at (0, 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

[1] 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, No. 1, pp. 27–52, 2009.
[2] G. Chartrand and O. R. Oellermann, Applied and algorithmic graph theory,
Vol. 993. McGraw-Hill New York, 1993.
[3] S.-Y. Hsieh and Y.-F. Weng, “Fault-tolerant embedding of pairwise independent
hamiltonian paths on a faulty hypercube with edge faults,” Theory of
Computing Systems, Vol. 45, No. 2, pp. 407–425, 2009.
[4] 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, 2007.
[5] S.-S. Kao and Pi-Hsiang, “Mutually independent hamiltonian cycles in k-ary
n-cubes when k is odd,” Proc. of the 2010 American conference on Applied
mathematics (AMERICAN-MATH 10), University of Harvard, Cambridge,
Cambridge, United States, pp. 116–121, January 27-29, 2010.
[6] T.-L. Kueng, T. Liang, and L.-H. Hsu, “Mutually independent hamiltonian
cycles of binary wrapped butterfly graphs,” Mathematical and Computer
Modelling, Vol. 48, No. 11-12, pp. 1814–1825, 2008.
[7] T.-L. Kung, C.-K. Lin, T. Liang, J. J. M. Tan, and Lih-Hsing, “Fault-free
mutually independent hamiltonian cycles of faulty star graphs,” International
Journal of Computer Mathematics, Vol. 88, No. 4, pp. 731–746, 2011.
[8] Y.-L. Lai, D.-C. Yu, and Lih-Hsing, “Mutually independent hamiltonian
cycle of burnt pancake graphs,” IEICE Transactions on Fundamentals of
81
Electronics, Communications and Computer Sciences, Vol. E94-A, No. 7,
pp. 1553–1557, 2011.
[9] F. T. Leighton, Introduction to parallel algorithms and architectures. Morgan
Kaufmann San Francisco, 1992.
[10] Y.-K. Shih, H.-C. Chuang, S.-S. Kao, and J. J. M. Tan, “Mutually independent
hamiltonian cycles in dual-cubes,” The Journal of Supercomputing,
Vol. 54, No. 2, pp. 239–251, 2010.
[11] H. Su, S.-Y. Chen, and S.-S. Kao, “Mutually independent hamiltonian cycles
in alternating group graphs,” The Journal of Supercomputing, Vol. 61, No. 3,
pp. 560–571, 2012.
[12] 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, 2011.
[13] 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, No. 02, pp. 235–255, 2006.
[14] K. W. Tang and S. A. Padubidri, “Diagonal and toroidal mesh networks,”
IEEE Transactions on Computers, Vol. 43, No. 7, pp. 815–826, 1994.
[15] Y.-H. Teng, J. J. Tan, T.-Y. Ho, and L.-H. Hsu, “On mutually independent
hamiltonian paths,” Applied Mathematics Letters, Vol. 19, No. 4, pp. 345–
350, 2006.
[16] K.-S. Wu and J. S.-T. Juan, “Mutually independent hamiltonian cycles of
Cm × Cn when m, n are odd,” Proc. of the 29th Workshop on Combinatorial
Mathematics and Computational Theory, National Taipei College of
Business, Taipei, Taiwan, pp. 165–170, April 27-28, 2012.
82
[17] K.-S. Wu and J. S.-T. Juan, “Mutually independent hamiltonian cycles of
Cn ×Cn,” Proc. of World Academy of Science, Engineering and Technology,
Vol. 65, Tokyo, Japan, pp. 754–760, May 29-30, 2012.
[18] K.-S. Wu and J. S.-T. Juan, “Mutually independent hamiltonian cycles of
Ck ×Ck+1,” Proc. of the 30th Workshop on Combinatorial Mathematics and
Computational Theory, National Dong Hwa University, Hualien, Taiwan,
pp. 302–310, April 26-78, 2013.
[19] K.-S. Wu and J. S.-T. Juan, “The mutually independent hamiltonianicity
of cartesian product graphs,” Proc. of Asian Association for Algorithms and
Computation 2013 (AAAC 2013), Matsushima, Japan, pp. 23, Apr. 19-21,
2013.
[20] 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, 2009.
[21] J.-M. Xu, Topological structure and analysis of interconnection networks.
Springer Publishing Company, Incorporated, 2010.
[22] 吳凱修, 王怡君, and 阮夙姿, “C2m+1 × C2m+1 上之互相獨立漢米爾頓迴
圈,” Proc. of the 28th Workshop on Combinatorial Mathematics and Computational
Theory, National Penghu University of Science and Technology,
Penghu, Taiwan, pp. 327–332, May 27-28, 2011.