增廣立方體中經(jīng)過給定三條邊的哈密爾頓圈

佘衛(wèi)強(qiáng)

（漳州職業(yè)技術(shù)學(xué)院 公共教學(xué)部，福建 漳州 363000）

增廣立方體中經(jīng)過給定三條邊的哈密爾頓圈

佘衛(wèi)強(qiáng)

（漳州職業(yè)技術(shù)學(xué)院 公共教學(xué)部，福建 漳州 363000）

用歸納假設(shè)法證明了結(jié)論：令 AQn是增廣立方體，當(dāng) n≥ 2時，若 Ee? E（ AQn），1≤≤ 3，這里 Ee是線性森林（每個分支都是路），則在 AQn中有哈密爾頓圈包含 Ee的所有邊.

增廣立方體；指定邊；哈密爾頓圈；互連網(wǎng)絡(luò)

1 引言

超大規(guī)模計算機(jī)系統(tǒng)和計算機(jī)互連網(wǎng)絡(luò)發(fā)展迅速，在并行處理和計算系統(tǒng)中超立方體拓?fù)浣Y(jié)構(gòu)發(fā)揮著重要的作用，是迄今最通用的網(wǎng)絡(luò)，但它也有一些缺點，因此，許多人針對這些缺點提出了一些推廣和變形網(wǎng)絡(luò)，如增廣立方體，折疊立方體等.增廣立方體網(wǎng)絡(luò)擁有直徑小，結(jié)構(gòu)對稱，高連通度和最大容錯性等性質(zhì)，增廣立方體的這些優(yōu)良性質(zhì)比超立方體更有競爭實力，因此，它成為了網(wǎng)絡(luò)中非常重要的一種拓?fù)浣Y(jié)構(gòu).國內(nèi)外對增廣立方體（容錯）路的研究已有多年，得到了很多的成果［2-4］.在網(wǎng)絡(luò)中考慮線性森林和多條路嵌入問題也得到了不少文章［5-7］.文中在 AQn中考慮了線性森林的問題得到以下定理：

定理1當(dāng) n≥ 2時，若 Ee? E（ AQn），1≤≤ 3，這里 Ee是線性森林（每個分支都是路），則在 AQn中有哈密爾頓圈C 包含 Ee的所有邊.

2 預(yù)備知識

本中術(shù)語和記號［1］，圖G的頂點集記為 V （G），邊集記為 E （G）；以x和y為端點的邊記為 （x， y）.給定子集 ε ?E（G），G的由ε導(dǎo)出的子圖記為 〈ε〉；從G中刪除ε中所有邊所得到的子圖記為 G-ε.若任取 x，y，其中 x ∈ V0，y ∈V1，在G中有一條哈密爾頓路連接x和y，則稱二部圖 G= （V0∪V1，E）為哈密爾頓可跡；對于每個 F? E（G）且≤ k，若 G- F仍哈密爾頓可跡，則稱圖G是k邊容錯哈密爾頓可跡.

將n維增廣立方體簡記為 AQn，A Qn遞歸地定義如下：A Q1是一個完全圖 K2，結(jié)點集｛0， 1｝，當(dāng) n≥2時， AQn可由兩個分別被標(biāo)記為 AQ和 AQ的 n-1階增廣立方體通過增加它們之間的 2 ×2n-1條邊獲得，增加這些邊的規(guī)定如下：令當(dāng)且僅當(dāng) AQ的頂點 u= 0un-1…u1與AQ的頂點 v= 1vn-1… v1滿足對于所有 i∈ ［1，n-1］，ui= vi（這種邊叫立方體邊，此時令 v= uh或 u= vh），或?qū)τ谒?i∈ ［1，n-1］，ui=（這種邊叫補(bǔ)邊，此時令 v=uc或u= vc），才會連接uv邊.把（u， uh）和（u， uc）統(tǒng)稱為交叉邊，記為 Ec.顯然 AQn-Ec= AQ∪ AQ，在 AQn中的每個頂點u都有兩條邊（u， uh）和（u， uc）.

引理1［2］當(dāng) n≥ 4時，增廣立方體 AQn是2 n- 4邊或邊容錯哈密爾頓可跡.AQ3是1點容錯哈密爾頓可跡；A Q3是2邊容錯哈密爾頓可跡；A Q2是1點容錯哈密爾頓可跡.

引理2［2］當(dāng) n ≥2時，設(shè)x0， x1， y0，y1是 AQn中任意4個頂點，則在 AQn中有兩條點不交路 P0和 P1，使得 V（ P0）∪V（ P1）=V（ A Qn），這里 P0連接 x0和 y0， P1連接 x1和 y1.

3 定理1證明

設(shè)（a， b） ∈ Ee，由歸納假設(shè)得，在 AQ中有哈密爾頓圈 C0包含 E0/（a， b）的所有邊.

3.1.1 若 （a， b）∈ C0.在 C0中取 （u0， v0）? E0，由引理1得，在 AQ中有一條哈密爾頓路 P1連接 uh和 vh，這里（uh，vh）是 （u0， v0）在 AQ的對應(yīng)邊.令，則在 AQn中有哈密爾頓圈C包含Ee的所有邊.

3.3.1.1 若 u0≠ w0且u1≠ w1.

3.3.1.2 若 u0= w0但u1≠ w1.

3.3.1.3 若 u0≠ w0但u1= w1.

3.4.1 若 u0≠ w0≠t0且u1≠ w1≠t1.

3.4.2 若 u0≠ w0≠t0且u1= w1≠t1.

3.4.3 若 u0≠ w0=t0且u1= w1≠t1.

定理1證畢.

［1］J.A.Bondy，U.S.R.Murty，Graph Theory with Applications［M］.New York：Macmillan Press，London，1976.

［2］H.C.Hsu，L.C.Chiang，J.J.M.Tan，et al，F(xiàn)ault Hamiltonicity of augmented cubes［J］.Parallel Computing，2005，31（1）：131-145.

［3］S.Y.Hsieh，Y.R.Cian，Conditional edge-fault Hamiltonicity of augmented cubes［J］.Inform.Sci.2010， 180：2596-2617.

［4］M.Ma，G.Liu，J.M.Xu，The super connectivity of augmented Cubes［J］.Inform.Process.Lett.2008，106：59-63.

［5］Wang.W.-Q.Chen X.-B.A faulty free哈密爾頓 cycle passing through prescribed edges in Hypercubes with faulty edges［J］.Inform.Process.Lett 2007，107：211-215.

［6］Chen X.-B.cycles passing through prescribed edges in hypercubes with some faulty edges［J］.Inform.Process.Lett 2007， 104（2）：211-215.

［7］S Wang，YYang，J Li.哈密爾頓 cycles passing through linear forests in k-ary nn-cubes［J］.Discrete Applied Mathematics， 2011，159（14）：1425-1435.

（責(zé)任編輯：季 平）

Hamilton Cycle Passing Through Prescribed Edges inAugmented Cube

SHE Wei-qiang
（Department of public teaching，Zhangzhou Institute of Technology，Zhangzhou 363000，China）

augmented cube；prescribed edge；Hamilton cycle；Interconnection networks

O157.5

A

1673-1417（2015）03-0010-06

10.13908/j.cnki.issn1673-1417.2015.03.0003

2015—08—20

福建省自然科學(xué)基金（2014J01018）

佘衛(wèi)強(qiáng)（1981—），男，福建東山人，講師，碩士。