A Simple Scheme of Generating Bipartite Graphs with Fault-tolerant Hamiltonian Properties

具容錯－漢米爾頓性質之二部圖的簡單建構方法

10.6358/JCYU.200503.0011

高欣欣(Shin-Shin Kao)；陳育志(Yu-Chih Chen)

二部圖 ； 漢米爾頓性質的 ； 漢米爾頓連通性 ； bipartite ； hamiltonian ； hamiltonian laceable

中原學報

33卷1期（2005 / 03 / 01）

11 - 19

英文

在這篇文章中，我們介紹一個産生有良好性質二的部圖的簡單方法。考慮一個bipartite圖形G，令W和B爲它的二個分部(partition)，假如它有1-edge hamiltonian，1(下標 p)-hamiltonian和hamiltonian laceable的性質，我們就稱它爲一個「良好的」二部圖。更明確的說，令F爲一個包含任意一個邊的集合，或F是一個包含一對點的集合{v1,v2|v1∈W, v2∈B}，若稱G是「良好的」，則G-F必保有漢米爾頓性質；而且在G中給定任意二點u∈W和v∈B，必存在從u到v的漢米爾頓路逕。我們稱此處所介紹的方法爲「邊代換」。兄弟樹[4]，BT(n)，n≥1就是一可由邊代換産生之良好的二部圖的例子。

In this paper, we introduce a simple scheme of generating ”good” bipartite graphs. A bipartite graph G with bipartition W and B is a good graph if it is 1-edge hamiltonian, 1(subscript p)-hamiltonian and hamiltonian laceable. More specifically, G is good if G-F remains hamiltonian where F consists of an edge or a pair of vertices {v1, v2|v1∈W, v2∈B}, and if there exists a hamiltonian path between u and v for any u∈W, v∈B. This scheme is called ”edge replacement”. Simple examples of good bipartite graphs, as well as the family of brother trees BT(n) with n≥1[4], are obtained as an application of edge replacement.