連結網路上的連通性相關之研究

Abstract

在本次計劃中，我們的主題是研究連接網路的連通性質。首先，我們提出一 個新的概念稱為泛可放置漢彌爾頓迴圈性質。若對圖G 中任兩點x 和y ，與任 意整數k 滿足d(x, y) ? k ? |V (G)| ? d(x, y)，都存在圖G 的一漢彌爾頓圈C 使得x、 y 和C 上的相關位置為k ，則我們稱這個漢彌爾頓圖G 為泛可放置。泛可放置漢 彌爾頓性質不僅承襲了漢彌爾頓性質，並且能有更進一步地延伸。我們已有初步 的成果，將繼續研究下去。 在這個計畫中，我們還要研討一個最近新提出的性質，稱為強Menger 連通性。 假設一網路G 有一壞點集合F, 令G-F 為移去F 之後的網路。若G-F 中每對點u 與v 被min{degf (u), degf (v)}點相異路徑所連接，其中degf (u)和degf (v)分 別為G-F 中u 與v 的分支度，則我們稱圖G 為強Menger 連通。 這些概念對於連結網路的研究是有趣且有用的。我們將在本次計劃中，將對 一些著名連結網路的泛可放置漢彌爾頓性質與強Menger 連通性質作深入的研 究。

In this project, we will study some connected properties of interconnection networks. First, we propose a new concept called panpositionable hamiltonicity. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and for any integer k satisfying d(x, y) . k . |V (G)| . d(x, y), there exists a hamiltonian cycle C of G such that the relative distance of x, y on C is k. The panpositionable hamiltonian property not only inherits the hamiltonian property but also advances it further. We already have some preliminary results, and we plan to do more study on this subject. We will also study the newly proposed concept called strong Menger connectivity. Suppose that a network G has a set F of faulty vertices and let G.F be the resulting network with those vertices in F removed. We say that a k-regular graph G is strongly Menger connected if each pair u and v of G.F are connected by min{degf (u), degf (v)} vertex-disjoint fault-free paths in G.F, where degf (u) and degf (v) are the degree of u and v in G . F, respectively. These concepts are both interesting and useful in the study of interconnection networks. In this project, we will study the panpositionable Hamiltonian property and the strong Menger property of many existing practical interconnection networks.