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

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 連通性質作深入的研 究。