故障3-元n-立方體的哈密頓圈嵌入

郭海寬

（太原師范學(xué)院 數(shù)學(xué)系，山西 太原 030012）

0 引言

因?yàn)榛ミB網(wǎng)絡(luò)上很多并行應(yīng)用，比如那些圖像和信號(hào)進(jìn)程最初都是以圈結(jié)構(gòu)進(jìn)行設(shè)計(jì)的，因此一個(gè)網(wǎng)絡(luò)具有有效的圈嵌入能力是非常重要的.人們對各種網(wǎng)絡(luò)的圈嵌入能力進(jìn)行了廣泛的研究［1-3］.本文考慮著名的超立方網(wǎng)絡(luò)的變形網(wǎng)絡(luò)3-元n-立方體.

本文所用到的術(shù)語和記號(hào)采用文獻(xiàn)［9］中的術(shù)語和記號(hào).圖G的頂點(diǎn)集和邊集分別用V（G）和E（G）表示.對一個(gè)子集F?V（G），用G-F表示從G中刪去F中所有點(diǎn)以及與F關(guān)聯(lián)的邊得到的子圖.

定義1 一個(gè)圖G被稱為哈密頓的，若G包含一個(gè)哈密頓圈.進(jìn)一步，若G的每一條邊在一個(gè)哈密頓圈上，則G被稱為是邊-哈密頓的；若至多除一條邊外，其余每一條邊在一個(gè)哈密頓圈上，則G被稱為是幾乎邊-哈密頓的.

若圖中一個(gè)點(diǎn)是故障的，我們認(rèn)為這個(gè)點(diǎn)以及它關(guān)聯(lián)的邊不存在.顯然具有故障點(diǎn)的圖是無故障圖的一個(gè)子圖.在本文中，故障中一條健康邊是指中一條不與故障點(diǎn)關(guān)聯(lián)的邊.

1 用到的引理

我們首先給出幾個(gè)重要的引理.

引理1［8］給定一個(gè)整數(shù)n≥2，令F是一個(gè)至多有2n-3個(gè)頂點(diǎn)的集合.對-F中任意兩個(gè)頂點(diǎn)s，t，-F中存在一條哈密頓路連接s和t.

由上面的引理，我們有如下推論.

推論1 給定一個(gè)整數(shù)n≥2，令F是一個(gè)至多有2n-3個(gè)頂點(diǎn)的集合.則-F是邊-哈密頓的.

證明 由對稱性，我們只需考慮情況F＝｛00，01｝和F＝｛00，11｝.如圖1（a）和圖2（a）所示.

圖1 當(dāng)F＝｛00，01｝時(shí)的哈密頓圈嵌入Fig.1 Embeddings of Hamiltonian cycle when F＝｛00，01｝

圖2 當(dāng)F＝｛00，11｝時(shí)的哈密頓圈嵌入Fig.2 Embeddings of Hamiltonian cycle when F＝｛00，11｝

給定一個(gè)整數(shù)n≥3，令F是一個(gè)具有2n-2個(gè)故障點(diǎn)的集合且e是-F中一條邊.我們有下面的兩個(gè)引理.

證明 令D1＝｛d：d是一個(gè)維數(shù)使得沿d-維將分成三個(gè)子立方后，e在某個(gè)子立方中｝.顯然，｜D1｜＝n-1.令D2＝｛d：d是一個(gè)維數(shù)使得沿d-維將分成三個(gè)子立方后，F(xiàn)中所有頂點(diǎn)在某個(gè)子立方中｝.由題意，我們只需要證明｜D1｜＞｜D2｜.

反證.設(shè)｜D2｜≥｜D1｜＝n-1.從的結(jié)構(gòu)和D2的定義不難看出F中所有頂點(diǎn)都在一個(gè)3-元（n-｜D2｜）-立方中.因此，｜D2｜＝n-1且F中所有頂點(diǎn)都在一個(gè)3-元1-立方中.然而，由n≥3，我們有｜F｜＝2n-2≥4＞3＝｜V）｜，矛盾.因此，存在一個(gè)維數(shù)使引理成立.

在下面的引理中，設(shè)Q［0］，Q［1］和Q［2］是帶故障點(diǎn)的一個(gè)劃分使得e在某個(gè)子立方中且對每一個(gè)i＝0，1，2都有｜Fi｜≤2n-3成立.

引理4 令e∈E（Q［i］），C是Q［i］-Fi的一個(gè)包含邊e的哈密頓圈.若｜Fi｜≤2n-4且對j∈｛i＋1，i-1｝有｜Fj｜≤2n-4成立，則C-e上存在一條邊（xi，yi）使得（xj，yj）是Q［j］中一條健康且非限制邊.

2 主要結(jié)果

本節(jié)將給出主要結(jié)果.

證明 我們用數(shù)學(xué)歸納法對n進(jìn)行歸納.當(dāng)n＝2時(shí)，由引理2知結(jié)論成立.下面假設(shè)n≥3且結(jié)論對成立，其中2≤m≤n-1，也就是說，在具有2m-2個(gè)故障點(diǎn)的中，每條健康且非限制邊在中一個(gè)哈密頓圈上.我們將證明定理對成立.設(shè)e是-F中任意一條邊.由引理3，我們可以沿某一維將分成三部分Q［0］，Q［1］和Q［2］使得e在某個(gè)子立方中且對每一個(gè)i＝0，1，2都有｜Fi｜≤2n-3成立.進(jìn)一步，不失一般性，假設(shè)e∈E（Q［i］），其中i∈｛0，1，2｝，且｜F0｜≥｜F1｜≥｜F2｜.我們下面分兩種情況進(jìn)行討論.

情況1 e是Q［i］中非限制邊.

情況1.1 ｜F0｜≤2n-4.

在這種情況下，｜Fi｜≤｜F0｜≤2n-4.由推論1和歸納假設(shè)知，e在Q［i］-Fi的一個(gè)哈密頓圈Ci上.由引理4，Ci-e上存在一條邊（ui，vi）使得（ui＋1，vi＋1）是Q［i＋1］-Fi＋1中非限制邊.類似的，（ui＋1，vi＋1）位于Q［i＋1］-Fi＋1的一個(gè)哈密頓圈Ci＋1上且Ci＋1-（ui＋1，vi＋1）上有一條邊（si＋1，ti＋1）使得（si＋2，ti＋2）是Q［i＋2］-Fi＋2中非限制邊.再次由推論1和歸納假設(shè)知，（si＋2，ti＋2）在Q［i＋2］-Fi＋2的一個(gè)哈密頓圈Ci＋2上.結(jié)合Ci-（ui，vi），Ci＋1-｛（ui＋1，vi＋1），（si＋1，ti＋1）｝和 Ci＋2-（si＋2，ti＋2）以及邊（ui，ui＋1），（vi，vi＋1），（si＋1，si＋2）和（ti＋1，ti＋2），我們可得到-F 的一個(gè)包含邊e的哈密頓圈.

情況1.2 ｜F0｜＝2n-3且e∈E（Q［0］）.

我們首先斷言Q［0］-F0有一條包含邊e的哈密頓路P0.令v＊∈F0.則｜F0＼｛v＊｝｜＝2n-4.由歸納假設(shè)，e在Q［0］-（F0＼｛v＊｝）的一個(gè)哈密頓圈C0上.注意到e不與v＊相關(guān)聯(lián).因此C0-v＊是Q［0］-F0的一條包含邊e的哈密頓路，記為P0.斷言成立.

設(shè)u0和v0是P0的兩個(gè)端點(diǎn).因?yàn)镼［0］外只有一個(gè)故障點(diǎn)v＊＊且｜F1｜≥｜F2｜，我們有｜F1｜＝｜｛v＊＊｝｜＝1且｜F2｜＝0.因此邊（u0，u2）和（v0，v2）都是健康邊.由引理1，Q［2］有一條從u2到v2的哈密頓路P2.在P2上選擇一條邊（s2，t2）使得（s1，t1）不與故障點(diǎn)v＊＊關(guān)聯(lián).因?yàn)?≤2n-5，故由引理1，Q［1］-v＊＊有一條從s1到t1的哈密頓路P1.因此，P0，P1和P2-（s2，t2）連同邊（u0，u2），（v0，v2），（s1，s2）和（t1，t2）組成-F的一個(gè)包含邊e的哈密頓圈.

情況1.3 ｜F0｜＝2n-3且e∈E（Q［1］）.

類似情況1.2，Q［0］-F0有一條包含邊e的從u0到v0的哈密頓路P0.因?yàn)椋麱1｜＝1，u1和v1至少有一個(gè)非故障.不失一般性，我們假設(shè)u1是非故障的.因?yàn)椋麱1｜＝1≤2n-5，由推論1，e在Q［1］-F1的哈密頓圈C1上.顯然，u1∈V（C1）.取u1在哈密頓圈C1上一個(gè)鄰點(diǎn)w1使得（u1，w1）≠e.

若w2≠v2，由引理1和｜F2｜＝0，我們可以得到Q［2］的一條從w2到v2的哈密頓路P2.此時(shí)，P0，C1-（u1，w1）和P2連同三條邊（u0，u1），（w1，w2）和（v0，v2）組成-F 的一個(gè)包含邊e的哈密頓圈.

下面設(shè)w2＝v2.選取P0上一條不與v0關(guān)聯(lián)的邊.顯然，v2?｛s2，t2｝.應(yīng)用引理1，我們可以得到Q［2］-v2的一條從s2到t2的哈密頓路P2.因此，P0，C1-（u1，w1）和P2連同五條邊（u0，u1），（w1，w2），（v0，v2），（s0，s2）和（t0，t2）組成-F 的一個(gè)包含邊e的哈密頓圈.

情況1.4 ｜F0｜＝2n-3且e∈E（Q［2］）.

類似情況1.2，Q［0］-F0有一條包含邊e的從u0到v0的哈密頓路P0.因?yàn)椋麱2｜＝0，e顯然在Q［2］的一個(gè)哈密頓圈C2上.

情況1.4.1 （u2，v2）∈E（C2）且（u2，v2）≠e.

此時(shí)，組合P0，C2-（u2，v2）和兩條邊（u0，u2），（v0，v2），我們得到-V（Q［1］）-F0的一個(gè)包含邊e的哈密頓圈C＊.選取P0上一條邊（s0，t0）使得（s1，t1）不與Q［1］中故障點(diǎn)關(guān)聯(lián)且令P1是Q［1］-F1的一條從s1到t1的哈密頓路.此時(shí)C＊-（s0，t0）和P1連同兩條邊（s0，s1），（t0，t1）組成-F 的一個(gè)包含邊e的哈密頓圈.

情況1.4.2 （u2，v2）∈E（C2）且（u2，v2）＝e.

令s2是u2在C2上的一個(gè)鄰點(diǎn)使得s2≠v2，t2是v2在C2上的一個(gè)鄰點(diǎn)使得t2≠u2.因?yàn)椋麱1｜＝1，故s1和t1至少有一個(gè)非故障.不失一般性，我們假設(shè)s1是非故障的.注意s1≠v1.

若v1非故障，由引理1，Q［1］-F1有一條從s1到v1的哈密頓路P1.因此，P0，C2-（u2，s2）和P1連同三條邊（u0，u2），（v0，v1）和（s1，s2）組成-F 的一個(gè)包含邊e的哈密頓圈.

若v1是故障點(diǎn)，則u1和t1都是非故障點(diǎn).因此Q［1］-F1有一條從u1到t1的哈密頓路P1′.從而P0，C2-（v2，t2）和P1′連同三條邊（u0，u1），（v0，v2）和（t1，t2）組成一個(gè)所求的哈密頓圈.

情況1.4.3 （u2，v2）?E（C2）.

在這種情況中，u2和v2至少有一個(gè)點(diǎn)不與邊e關(guān)聯(lián).不失一般性，設(shè)v2不與邊e關(guān)聯(lián).取u2在C2上的一個(gè)鄰點(diǎn)s2使得（u2，s2）≠e，取v2在C2上的一個(gè)鄰點(diǎn)t2使得C2上兩條從u2到v2的路分別包含點(diǎn)s2和t2.因?yàn)関2不與邊e關(guān)聯(lián)，故（v2，t2）≠e.

因?yàn)椋鹵1，t1｝∩｛v1，s1｝＝?且｜F1｜＝1，故要么u1和t1是非故障的，要么v1和s1是非故障的.不失一般性，我們設(shè)前者成立，即u1和t1是非故障的.則Q［1］-F1有一條從u1到t1的哈密頓路P1.因此P0，C2-（v2，t2）和P1連同三條邊（u0，u1），（v0，v2）和（t1，t2）組成一個(gè)所求的哈密頓圈.

情況2 e在Q［i］中是限制邊.

令e＝（x，y）.由限制邊的定義知，Q［i］至少有2n-4個(gè)故障點(diǎn)與同一個(gè)頂點(diǎn)z相鄰且（x，y，z，x）是Q［i］-Fi中一個(gè)長為3的圈.令d是一個(gè)維數(shù)使得z的兩個(gè)由d-維邊連接的鄰點(diǎn)都故障.沿d-維將劃分成另外三個(gè)子立方Q′［0］，Q′［1］和Q′［2］.容易看到，e＝（x，y）在某個(gè)子立方Q′［i］中，i∈｛0，1，2｝，且對每一個(gè)j＝0，1，2都有｜F∩V（Q′［j］）｜≤2n-4成立.因?yàn)閑在中非限制，故z在Q′［i］中至少有一個(gè)非故障鄰點(diǎn).這就意味著e在Q′［j］中是非限制邊.類似情況1.1中的證明，我們可以得到所求的哈密頓圈.

推論3［10］設(shè)n≥2，則具有至多2n-2個(gè)故障點(diǎn)的是哈密頓的.

［1］Tsai C H.Fault-tolerant Cycles Embedded in Hypercubes with Mixed Link and Node Failures［J］.Applied Mathematics Letters，2008，21：855-860.

［2］Roman C，Evelynie F，Li H.Hamiltonicity and Pancyclicity of Cartesian Products of Graphs［J］.Discrete Mathematics，2009，22：6337-6343.

［3］Qu Ellen X Y，Wang J L.Vertex Pancyclicity in Quasi-claw-free Graphs［J］.Discrete Mathematics，2009，309：1135-1141.

［4］Bae Myung M，Bose B.Edge Disjoint Hamiltonian Cycles in k-ary n-cubes and Hypercubes［J］.IEEE Transactions on Computers，2003，52：1271-1284.

［5］Yaagoub A A，Stewart L A.Fault-tolerant Embeddings of Hamiltonian Circuits in k-ary n-cubes［J］.SIAM Journal on Discrete Mathematics，2002，15：317-328.

［6］Hsieh S Y，Lin T J，Huang H L.Panconnectivity and Edge-Pancyclicity of 3-Ary n-cubes［J］.Journal of Supercomputing，2007，42：225-233.

［7］Stewart L A，Xiang Y H.Bipanconnectivity and Bipancyclicity in k-ary n-cubes［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20：25-33.

［8］Wang S Y，Lin S W.Path Embeddings in Faulty 3-ary n-cubes［J］.Information Sciences，2010，180：191-197.

［9］Bondy J A，Murty U S R.Graph Theory［M］.New York：Springer，2007.

［10］Yang M C，Tan J J M，Hsu L H.Hamiltonian Circuit and Linear Array Embeddings in Faulty k-ary n-cubes［J］.Journal of Parallel and Distributed Computing，2007，67：362-368.