点故障3－ary n 立方体中经过指定路的无故障哈密尔顿圈①

佘卫强

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

0 引 言

随着计算机系统规模的扩大，系统中出现计算机故障或计算机间线路故障的可能性随之增加，因此，网络的(容错)路问题也成了人们关注的研究点.3－ary n 立方体和超立方体网络具有结构对称，高连通度和最大容错性等优良性质，因此，它们都是网络中非常重要的拓扑结构.国内外对3－ary n 立方体和超立方体(容错)路的研究已有多年，得到了很多的成果，如:Yang 在文献［1］中研究了故障点或边的k－ary n 立方体中圈和路的嵌入问题.文献［2 ～3］研究了线性森林嵌入问题.文献［4 ～5］研究了多条不交路问题.本文研究了含有点故障Q3n 中经过指定路的无故障哈密尔顿圈问题.得到如下结果:

1 预备知识

本文的图文术语和记号见文献［6］，一个图G的顶点集记为V(G)，边集记为E(G);以x 和y 为端点的边记为(x，y).给定子集ε ⊆E(G)，G 的由ε 导出的子图记为＜ε ＞;从G 中删除ε 中所有边所得到的子图记为G－ε.k－ary n 立方体简称为，它的每个节点T 由一个n 位k 进制字符串(a1，a2，…，an)，0 ≤ai＜k，1 ≤i ≤n，i 称为节点T 的第i 维.任意两点X=(x1，x2，…，xn)与Y=(y1，y2，…，yn)之间有边，当且仅当存在一个整数j(1≤j ≤n)，使得xj=yj±1(mod k)且xh=yh对于每个h ∈{1，2，…，n}－{j}.显然，当k=2是n 正则图，当k ≥3，是2n 正则图，且的直径为n×［k/2］(见文献［6］)，若，而xj=yj，j ∈{1，2，…，n}－{i}，其中1 ≤i ≤n，则称边(X，Y)为第i 维边，中所有第i 维边的集合记为Ei.显然，沿第i 维边可将分成k 个不交子图这里是由第i个比特位xi=j 的所有顶点导出的子图.

引理1 (见文献［1］)当n ≥2 时，设|F|=|Fv|+|Fe|≤2n－3，设x 和y 是中两个顶点，则在中存在一条长为l 的路P 连接x 和y，这里

2 定理1 证明

当h=1 时，|F0|≤2n－3，由引理1 得，定理1 成立.故只需证当2 ≤h ＜n，|F|≤2n－(2h+1)时，定理1 成立即可.

对n 作归纳法证明.

由引理1 得，当n=3 时，则h=2，|F|≤1，设P=(u0，v0，w0)，令s0与u0相邻且，由引理1 得，在在－F－u0－v0中存在无故障哈密尔顿路连接s0与w0，所以定理1 成立.

由h ＜n，则存在j(1 ≤j ≤n)使得|Ej∩P|=0，这里Ej是j 第维的所有边，沿第j 维将分成三个不交的，(简记为Q［0］，Q［1］，Q［2］)，不失一般性，假设路P 包含Q［0］中，由于是点可迁，故只需考虑以下三种情况(其他情况讨论类似).

情况1:|F0|≤2n－(2h+1)－2.因|F0|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由归纳假设得，在Q［0］－F0中存在长为3n－1－|F0|无故障哈密尔顿圈C 包含路P.因2 ≤h，所以|F1|≤2n－5 或|F2|≤2n－5，由3n－1－|F0|－h－2|F1|＞0，在Q［0］－F0中存在(w0，s0)∈E(C0－P)使得(w1，s1)无故障，这里(w1，s1)是(w0，s0)在Q［1］－F1的对应边，由引理1 得，在Q［1］－F1中有哈密尔顿路P1连接w1和s1.由3n－1－|F1|－2|F2|＞0，在Q［1］－F1中存在(u1，v1)∈E(P1)使得(u2，v2)无故障，这里(u2，v2)是(u1，v1)在Q［2］－F2的对应边，由引理1 得，在Q［2］－F2中有哈密尔顿路P2连接u2和v2.则哈密尔顿圈C0∪P1∪P2－(w0，s0)－(u1，v1)+(w0，w1)+(s0，s1)+(u1，u2)+(v1，v2)满足定理要求.

情况2:|F0|=2n－(2h+1)－1.

不失一般性，设|F1|=1，|F2=0，t0∈F0，因|F0/t0|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由归纳假设得，在Q［0］－F0/t0中存在长为3n－1－|F0/t0|无故障哈密尔顿圈C0包含路P.不失一般性，设哈密尔顿圈C0中t0的相邻顶点为u0，v0，这里u2，v2分别是u0，v0在Q［2］的对应点，由引理1 得，在Q［1］－F1中有哈密尔顿圈C1，取(w1，s1)∈E(C0)使得(w1，s1)在Q［2］的对应边(w2，s2)且使，由引理2 得，在Q［2］中存在两条点不交的路和，使得，这里连接w2和连接s2和v2.则哈密尔顿圈s2)+(u0，u2)+(v0，v2)满足定理要求.

情况3:|F0|=2n－(2h+1).

设x0，y0∈F0，因|F0/(x0+y0)|≤2n－(2h+1)－2=2(n－1)－(2h+1)，又h ＜n－1，由归纳假设得，在Q［0］－F0/(x0+y0)中存在无故障哈密尔顿圈C0包含路P.以下就x0，y0在哈密尔顿圈C0中的位置分三种情况讨论

3.1 若C0 =(…u0，x0，v0，…，w0，y0，s0，…)

由引理1 得，在Q［1］中有哈密尔顿路P1连接w1和s1，这里w0，s0在Q［1］的对应点分别为w1，s1，由引理1 得，在Q［2］中有哈密尔顿路P2连接u2和v2.这里u0，v0在Q［2］的对应点分别为u2，v2，则哈密尔顿圈C0∪P1∪P2+(v0，v2)+(w0，w1)+(s0，s1)+(u0，u2)－(u0，x0，v0)－(w0，y0，s0)满足定理要求.

3.2 若C0 =(…u0，x0，v0，u0，w0，…)

由引理1 得，在Q［1］中有哈密尔顿路P1连接w1和v1，这里w0，v0在Q［1］的对应点分别为w1，v1，由引理1 得，在Q［2］中有哈密尔顿路P2连接u2和v2.这里u0，v2在Q［2］的对应点分别为u2，v2，则哈密尔顿圈C0∪P1∪P2+(w0，w1)+(v0，v1)+(u0，u2)+(v0，v2)－(u0，x0，v0)－(v0，y0，w0)满足定理要求.

3.3 若C0 =(…u0，x0，y0，v0，…)

由引理1 得，Q［1］在中有哈密尔顿路P1连接u1和v1，这里u0，v0在Q［1］的对应点分别为u1，v1，取(w1，s1)∈E(P1)，由引理1 得，在Q［2］中有哈密尔顿路P2连接w2和s2.这里(w2，s2)是(w1，s1)在Q［2］的对应边，则哈密尔顿圈C0∪P1∪P2－(u0，x0，y0，v0)+(u0，u1)+(v0，v1)+(w1，w2)+(s1，s2)满足定理要求.

说明:若|F|=2n－(2h+1)+2，当h=1 时，即|F|=2n－1，显然结论不成立.若|F|=2n－(2h+1)+1，假设h=1 时，当n=2 时，易证结论成立.当n ≥3 时，结论是否成立仍有待研究.

［1］ Yang M.C.，Tan 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，(4):362－368.

［2］ Yuxing Yang，Shiying Wang.Fault－free Hamiltonian Cycles Passing Through a Linear Forest in Ternary n－cubes with Faulty Edges［J］.Theoretical Computer Science，2013，491:78－82.

［3］ Shiying Wang，Yuxing Yang，Jing Li，Shangwei Lin.Hamiltonian Cycles Passing Through Linear Forests in k－ary n－cubes［J］.Discrete Applied Mathematics，2011，159:1425–1435.

［4］ 佘卫强.点故障3－ary n 立方体中两条无故障 点不交路［J］.佳木斯大学学报，2013，(11):829－932.

［5］ Shurong Zhang，Shiying Wang.Hamiltonian Cycles Passing Through Linear Forests in k－ary n－cubes［J］.Discrete Applied Mathematics，2011，159:1425–1435.

［6］ Bondy J.A.，Murty U.S.R.Graph Theory with Applications，Macmillan Press，London，1976.