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

在這篇文章中，我們介紹一個産生有良好性質二的部圖的簡單方法。考慮一個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.

並列關鍵字

bipartite ； hamiltonian ； hamiltonian laceable

國際替代計量

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

全文下載

主題瀏覽