笛卡爾積圖之漢彌爾頓性刻畫

Abstract

本篇論文主要討論一類特別的圖：笛卡爾積圖。首先，對於樹狀圖與圈狀圖的笛卡爾積，我們討論它的漢彌爾頓性及邊漢彌爾頓性。其次，對於樹狀圖與路徑圖的笛卡爾積，討論其漢彌爾頓性及偶泛圈性。在第二類圖中，我們將樹狀圖分為可完美配對或存在路徑因子兩情況討論，並且用系統性的方法建構出此二圖類的漢彌爾頓圈。論文內亦在已知定理的基礎上補充進一步的結果並且給予新證明方法，尤其證明了在所有討論的圖類中，圖為漢彌爾頓圖與圖為１堅韌兩條件為等價。

The Cartesian product of two graphs forms a special class of graphs. First,for a given tree through its Cartesian products withcycles, we discuss its Hamiltonicity and edge-Hamiltonicity. Second, for a given tree through its Cartesian products with paths, we discuss its Hamiltonicity and even-pancyclicity. We find several Hamiltonian graphs in the case that the tree has a perfect matching or a path factor. Some well-known results which have been proved are also given in this thesis with modified results or new approach of proofs. In particular, we prove that the two conditions Hamiltonian and 1-tough are equivalent in those graphs we discussed.