滿足奧爾條件圖形之兩點容錯漢米爾敦性及互相獨立之漢米爾敦迴圈數

On the Two-vertex Fault Hamiltonicity for Graphs Satisfying Ore's Theorem and the Number of Mutually Independent Hamiltonian Cycles

潘秀君(Hsiu-Chunj Pan)

指導教授 ： 高欣欣

共同指導教授 ： 蘇珣(Hsun Su)

中原大學/理學院/應用數學研究所/博士(2022年)

https://doi.org/10.6840/cycu202200030

摘要

本論文主要研究滿足奧爾條件圖形之某些漢米爾敦特性。文中首先說明漢米爾敦之定義，任何無方向的簡單圖形 G = (V, E), 其中 V 及 E 代表圖形G的頂點集合及邊集合, 如果它包含一個經過每一頂點剛好一次的迴路，則稱該圖形為漢米爾敦圖。奧爾已證明如果圖形 G 滿足 〖deg〗_G(u) + 〖deg〗_G(v)≥|G|，則G為漢米爾敦圖，其中 u 及 v 為頂點集合中兩個不相鄰的頂點。|G|是圖形G 之不同頂點的總數。蘇珣、石圜鋼、高欣欣三人已證明滿足奧爾條件的任一圖形G在移除任一頂點 x 後，仍為漢米爾敦圖，除非圖形G為兩種例外族群之一。 本論文中我們證明圖形G在移除任二頂點 x 及 y 後，仍為漢米爾敦圖，除非G屬於八種例外族群之一，以η_i表示出此八種例外族群，整數 “i”在大於等於1，且小於等於8的範圍之中。
其次，任意給定一無方向的簡單圖形 G = (V, E), |G|代表圖形中所有點的總數，C_1與C_2是G中兩個始於頂點 x 的漢米爾敦迴路，C_1=⟨u_1, u_2, . . . , u_"|G|" , u_1⟩，C_2=⟨v_1, v_2, . . . , v_"|G|" , v_1⟩，且 x =u_1=v_1。如果對於每一個整數 “i”，i 在大於等於2，且小於等於|G|的範圍之中，都會有 “u_i≠v_i”的現象，則稱C_1與C_2相互獨立。{C_1, C_2, . . . , C_k}是G之漢米爾敦迴路所成的集合，若其中任意兩個迴路，皆是相互獨立，則稱這個集合為互相獨立。
徐力行和林政寬已證明，當圖形上有一點x，其〖deg〗_G(x)=|G|/2時，且G−{x}仍然是漢米爾敦圖，則通過點x的相互獨立的漢米爾敦迴路有一條。本論文發現如果圖中有一點y，其〖deg〗_G(y)= |G|−1，且存在一個G−{x, y}之漢米爾敦迴路 C = ⟨v_1, v_2,…, v_("|G|" -2), v_1⟩，則通過點x的相互獨立的漢米爾敦迴路的個數，會隨著|G|的增大而增大。我們有系統的找出來，通過x的相互獨立的漢米爾敦迴路個數的下界，及|G|與此下界的關係。

關鍵字

點的度數 ； 奧爾條件 ； 漢米爾敦 ； 單點容錯漢米爾敦性 ； 雙點容錯漢米爾敦性 ； 相互獨立的漢米爾敦迴路 ； V2-圖 ； 迴路

並列摘要

Any undirected and simple graph G = (V, E), where V and E denote the vertex set and the edge set of G, is called Hamiltonian if it contains a cycle that visits each vertex of G exactly once. Ore proved that G is Hamiltonian if 〖deg〗_G(u)+〖deg〗_G(v)≥|G| holds for every nonadjacent pair of vertices u and v in V , where |G| is the total number of distinct vertices of G. Hsun Su, Yuan-Kang Shih, and Shin-Shin Kao proved that any graph G satisfying Ore’s condition remains Hamiltonian after removing any one vertex x ∈ V unless G belongs to one of two exceptional families of graphs. In this dissertation, we prove that G  {x, y} is Hamiltonian for any two vertices x, yV, unless G belongs to one of the eight exceptional families of graphs, denoted by η_i, where i∈{1,…, 8}.
For any undirected and simple graph G = (V, E), two Hamiltonian cycles of G beginning at a vertex x, C_1=⟨u_1, u_2, . . . , u_"|G|" , u_1⟩ and C_2=⟨v_1, v_2, . . . , v_"|G|" , v_1 ⟩ are independent if x =u_1=v_1 and u_i≠v_i for every i, 2≤i≤ |G|. A set of Hamiltonian cycles {C_1, C_2, . . . , C_k} of G are mutually independent if they are pairwise independent.
Lih-Hsing Hsu and Cheng-Kuan Lin have proved that, when there is a vertex x in G with 〖deg〗_G(x)=|G|/2 and G−{x} is Hamiltonian, then the number of mutually independent Hamiltonain cycles passing through x is one. In this dissertation, we find that if there is a vertex y in G with 〖deg〗_G(y)= |G|−1, and there exists a Hamiltonian cycle C = ⟨v_1, v_2,…, v_("|G|" -2), v_1⟩ of G−{x, y}, then the number of mutually independent Hamiltonain cycles passing through x will increase as |G| increases. We systematically find out the lower bound of the number of mutually independent Hamiltonain cycles beginning at x, and the relationship between |G| and the lower bound of the number of mutually independent Hamiltonain cycles beginning at x.

並列關鍵字

degree ； Ore's condition ； Hamiltonian ； 1-vertex fault Hamiltonian ； 2-vertex fault Hamiltonian ； mutually independent Hamiltonian cycle ； V2-graph ； cycles

參考文獻

References

[1] A. Ainouche, “Connectivity, independent sets and maximal circuits in undirected graphs,” Ph.D. Thesis, London University, 1980.

[2] A. Ainouche and N. Christofides, “Conditions for the existence of Hamiltonian circuits in graphs based on vertex degrees,” Journal of the London Mathematical Society, Vol. 32, 1985, pp. 385-391.

[3] J.A. Bondy and V. Chvátal, “A method of graph theory,” Discrete Mathematics, Vol. 15, 1976, pp. 111-136.

[4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, North Holland, N. Y., 1976. Retrieved from https://www.zib.de/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf