增強立方體之最大區域連通性質

Abstract

連通性在連結網路中是很重要的問題。Choudum和Sunitha在2002年時提出了增強立方體AQn並指出增強立方體具有以下性質: (1)當n>=4時，對AQn中任意壞點所成的集合F而言，若壞點個數總和不超過2n-2，則AQn-F為一包含2n-|F|個點的連通單元。(2)當n>=4時，AQn中任意兩點u和v之間，存在2n-1條點不相交路徑。在本篇論文中，我們提供了更進一步的結果，包括 (1)當n>=4時，對AQn中任意壞點所成的集合F而言，若壞點個數總和不超過4n-9，則AQn-F中的最大連通單元至少有2n-|F|-1個點。(2)當n>=4時，對AQn中任意壞點所成的集合F而言，若壞點個數總和不超過2n-7時，則對於AQn中任意兩個非壞點u和v之間，存在min{degf(u),degf(v)}條點不相交且無壞點路徑。

Connectivity is an important issue in interconnection networks. In 2002, Choudum and Sunitha proposed the augmented cube AQn and indicated that it has the following properties: (1) for any faulty vertex set F and |F|<= 2n-2 for n>=4, AQn-F is a connected component with 2n-|F| vertices; and (2) for any two vertices u and v of AQn with n>=4, there are 2n-1 vertex-disjoint paths joining u and v. In this paper, we show some further results about (1) for any faulty vertex set F and |F|<=4n-9 for n>=4, the maximal connected component of AQn-F has at least 2n-|F|-1 vertices; and (2) for any faulty vertex set F and |F|<=2n-7 for n>=4, each pair of non-faulty vertices u and v in AQn-F is connected by min{degf(u),degf(v)} vertex-disjoint fault-free paths.