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

Hamiltonian properties of Cartesian product graphs

高至芃(Kao, Louis)

指導教授 ： 翁志文

國立交通大學/理學院/應用數學系暨研究所/碩士(2016年)

摘要

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

關鍵字

漢彌爾頓性 ； 邊漢彌爾頓性 ； 偶泛圈性 ； 笛卡爾積 ； 路徑因子 ； 圖韌性

並列摘要

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.

並列關鍵字

Hamiltonicity ； edge-Hamiltonicty ； even-pancyclicity ； Cartesian product ； path factor ； graph toughness

參考文獻

sian product. Inform. Process.Lett., 96 (2005),pp.49-53

[1] J. Akiyama,M.Kano, Path factorsofagraph.GraphTheoryanditsApplications,

Wiley,NewYork(1984)

[2] V. Batagelj,T.Pisanski,HamiltoniancyclesintheCartesianproductofatreeand

a cycle. DiscreteMath., 38.2 (1982),pp.311-312.