篇名 | A Simple Scheme of Generating Bipartite Graphs with Fault-tolerant Hamiltonian Properties |
---|---|
卷期 | 33:1 |
並列篇名 | 具容錯--漢米爾頓性質之二部圖的簡單建構方法 |
作者 | 高欣欣 、 陳育志 |
頁次 | 11-19 |
關鍵字 | 二部圖 、 漢米爾頓性質的 、 漢米爾頓連通性 、 Bipartite 、 Hamiltonian 、 Hamiltonian laceable |
出刊日期 | 200503 |
在這篇文章中,我們介紹一個產生有良好性質的二部圖的簡單方法。考慮一個bipartite圖形G,令W和B為它的二個分部 (partition),假如它有1-edge hamiltonian,1p-hamiltonian和hamiltonian laceable的性質,我們就稱它為一個「良好的」二部圖。更明確的說,令F為一個包含任意一個邊的集合,或F是一個包含一對點的集合{v1, v2|v1[9465]W, v2[9465]B},若稱G是「良好的」,則G-F必保有漢米爾頓性質;而且在G中給定任意二點u[9465]W和v[9465]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, 1p-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 {u1, u2|u1[9465]W, u2[9465]B}, and if there exists a hamiltonian path between u and u for any u[9465]W, u[9465]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.