增广立方体中经过给定三条边的哈密尔顿圈

佘卫强

（漳州职业技术学院 公共教学部，福建 漳州 363000）

增广立方体中经过给定三条边的哈密尔顿圈

佘卫强

（漳州职业技术学院 公共教学部，福建 漳州 363000）

用归纳假设法证明了结论：令 AQn是增广立方体，当 n≥ 2时，若 Ee⊂ E（ AQn），1≤≤ 3，这里 Ee是线性森林（每个分支都是路），则在 AQn中有哈密尔顿圈包含 Ee的所有边.

增广立方体；指定边；哈密尔顿圈；互连网络

1 引言

超大规模计算机系统和计算机互连网络发展迅速，在并行处理和计算系统中超立方体拓扑结构发挥着重要的作用，是迄今最通用的网络，但它也有一些缺点，因此，许多人针对这些缺点提出了一些推广和变形网络，如增广立方体，折叠立方体等.增广立方体网络拥有直径小，结构对称，高连通度和最大容错性等性质，增广立方体的这些优良性质比超立方体更有竞争实力，因此，它成为了网络中非常重要的一种拓扑结构.国内外对增广立方体（容错）路的研究已有多年，得到了很多的成果［2-4］.在网络中考虑线性森林和多条路嵌入问题也得到了不少文章［5-7］.文中在 AQn中考虑了线性森林的问题得到以下定理：

定理1当 n≥ 2时，若 Ee⊂ E（ AQn），1≤≤ 3，这里 Ee是线性森林（每个分支都是路），则在 AQn中有哈密尔顿圈C 包含 Ee的所有边.

2 预备知识

本中术语和记号［1］，图G的顶点集记为 V （G），边集记为 E （G）；以x和y为端点的边记为 （x， y）.给定子集 ε ⊆E（G），G的由ε导出的子图记为 〈ε〉；从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，结点集｛0， 1｝，当 n≥2时， AQn可由两个分别被标记为 AQ和 AQ的 n-1阶增广立方体通过增加它们之间的 2 ×2n-1条边获得，增加这些边的规定如下：令当且仅当 AQ的顶点 u= 0un-1…u1与AQ的顶点 v= 1vn-1… v1满足对于所有 i∈ ［1，n-1］，ui= vi（这种边叫立方体边，此时令 v= uh或 u= vh），或对于所有 i∈ ［1，n-1］，ui=（这种边叫补边，此时令 v=uc或u= vc），才会连接uv边.把（u， uh）和（u， uc）统称为交叉边，记为 Ec.显然 AQn-Ec= AQ∪ AQ，在 AQn中的每个顶点u都有两条边（u， uh）和（u， uc）.

引理1［2］当 n≥ 4时，增广立方体 AQn是2 n- 4边或边容错哈密尔顿可迹.AQ3是1点容错哈密尔顿可迹；A Q3是2边容错哈密尔顿可迹；A Q2是1点容错哈密尔顿可迹.

引理2［2］当 n ≥2时，设x0， x1， y0，y1是 AQn中任意4个顶点，则在 AQn中有两条点不交路 P0和 P1，使得 V（ P0）∪V（ P1）=V（ A Qn），这里 P0连接 x0和 y0， P1连接 x1和 y1.

3 定理1证明

设（a， b） ∈ Ee，由归纳假设得，在 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的对应边.令，则在 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，Fault 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.

（责任编辑：季 平）

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

福建省自然科学基金（2014J01018）

佘卫强（1981—），男，福建东山人，讲师，硕士。