交换超立方体的哈密顿Laceability和强哈密顿Laceability＊

卢晓丽， 刘保冬

(浙江师范大学数理与信息工程学院，浙江金华 321004)

交换超立方体的哈密顿Laceability和强哈密顿Laceability＊

卢晓丽， 刘保冬

(浙江师范大学数理与信息工程学院，浙江金华 321004)

交换超立方体EH(s，t)是超立方体的一个变型.证明了：当s，t≥2时，EH(s，t)是哈密顿Laceable，并且也是强哈密顿Laceable.

互连网络;交换超立方体;哈密顿Laceability;强哈密顿Laceability

由EH(s，t)的定义知，它是具有2s+t+1个顶点、(s+t+2)2s+t-1条边的二部图.将二部图记为G=(V1，V2;E)，其中 V1和 V2是图的顶点集合的二部划分.用 P=〈u，P1，s，t，P2，v 〉表示一条以 u，v为端点的(u，v)-路，其中P1和P2分别表示路P中u到s和t到v的子路.若V(P)=V(G)，则称路P是哈密顿路.在二部图中，若对不同部分的任意2个顶点u∈V1，v∈V2，图中存在哈密顿(u，v)-路，则称二部图是哈密顿 laceable［3］.若二部图是哈密顿 laceable，且对同一部分的任意 2 个点 u，v∈Vi，i∈{1，2}，图中存在一条长为|G|-2的(u，v)-路，则称二部图是强哈密顿laceable［4］.近年来，学者研究了许多图类的哈密顿laceability及强哈密顿 laceability.例如，Hsieh等［5］研究了折叠立方体的强哈密顿 laceability;Huang［6］研究了偶k元n立方体的强哈密顿laceability.本文研究EH(s，t)的哈密顿laceability及强哈密顿laceability.

在给出主要结果之前，先引入一些有用的引理.

引理1［2］EH(s，t)同构于 EH(t，s).

引理2［2］EH(s，t)可分解为 2 个 EH(s-1，t)或 2 个 EH(s，t-1).

由引理2知，EH(k+1，t)可由2个EH(k，t)构成.为方便定理的证明，引入以下记号.

记 EH(k+1，t)=L⊙R，L 和 R 是 EH(k+1;t)的子图，VL={0ak…a1bt…b1c|ai，bj，c∈{0，1}，i∈［1，k］，j∈［1，t］}，VR={1ak…a1bt…b1c|ai，bj，c∈{0，1}，i∈［1，k］，j∈［1，t］}.

根据EH(k+1，t)的定义，由VL或VR导出的子图L和R都同构于EH(k，t)，且EH(k+1，t)中位于L和R之间的边属于E3.

引理3EH(2，2)是哈密顿laceable和强哈密顿laceable.

证明 先证 EH(2，2)是点可迁的.对点 u=a2a1b2b1c1∈V(EH(2，2))，令 σ(x2x1y2y1c)=(x2⊕a2)(x1⊕a1)(y2⊕b2)(y1⊕b1)(c⊕c1)，其中⊕表示模2加法.易证σ是EH(2，2)的一个自同构，使得点u=a2a1b2b1c1同构于点00000，故EH(2，2)是点可迁的.

表1构造了点00000到与它不同部分的点的哈密顿路.因为EH(2，2)是点可迁的，所以EH(2，2)是哈密顿laceable.表2给出了点00000到与它在同一部分的点的长为30的路.因为EH(2，2)是点可迁的，所以EH(2，2)是强哈密顿laceable.引理3证毕.

定理 1当 s，t≥2 时，EH(s，t)是哈密顿 laceable.

证明 由引理1知，EH(s，t)同构于EH(t，s)，因此只要对s进行归纳证明即可.当s=2时，由引理 3知，EH(2，2)是哈密顿 laceable.

假设当3≤s≤k时，EH(s，t)是哈密顿 laceable.下证当 s=k+1 时，EH(k+1，t)是哈密顿 laceable.设V1和V2是EH(k+1，t)的顶点集合的二部划分.要证EH(k+1，t)是哈密顿laceable，只要证任意u∈V1，v∈V2，EH(k+1，t)中存在一条哈密顿(u，v)-路即可.

考虑到EH(k+1，t)=L⊙R，分下面2种情形来证明.

情形 1u∈VL，v∈VR.

在VL中存在顶点uL，使得uL∈V2且uL在R中有邻点uR.由归纳假设知，在L中有一条哈密顿(u，uL)-路 P'，在 R 中有一条哈密顿(uR，v)-路 P"，则 P=〈u，P'，uL，uR，P"，v 〉为 EH(k+1，t)中的一条哈密顿(u，v)-路.

情形2点u，v都在VL或VR中，不妨设u，v都在VL中.

由归纳假设，在L中有一条哈密顿(u，v)-路P'.

断言 1：E(P')∩E3≠Ø.

否则，设 w 和 z是路 P'上的2 个顶点，则 w［s+t：t+1］=z［s+t：t+1］，故|P'|≤2t+1＜2k+t+1，这与

为EH(k+1，t)的一条哈密顿(u，v)-路.定理1证毕.P'是L中的哈密顿路矛盾.因此断言1成立.

设(uL，vL)∈E(P')∩E3.由EH(k+1，t)的定义知，uL和 vL在 R 中都有邻点，分别设为 uR和 vR.它们在R中相邻，由归纳假设知，在R中有一条哈密顿(uR，vR)-路P".设 P'中的(u，uL)和(vL，v)子路分别为 P'1和 P'2，则

表1 点00000到与它在不同部分的点的哈密顿路

表2 点00000到与它在同一部分的点的长为30的路

定理2当 s，t≥2时，EH(s，t)是强哈密顿 laceable.

证明 由引理1知，EH(s，t)同构于EH(t，s)，因此只要对s进行归纳证明即可.当s=2时，由引理 3知，EH(2，2)是强哈密顿 laceable.假设当 3≤s≤k时，EH(s，t)是强哈密顿 laceable.下证当 s=k+1时EH(k+1，t)是强哈密顿laceable.

只要证对任意 u，v∈Vi(i∈{1，2})，EH(k+1，t)中存在一条长为 2k+t+2-2 的(u，v)-路即可.不妨设u，v∈V1.考虑到 EH(k+1，t)=L⊙R，分下面2 种情形来证明.

情形 1u∈VL，v∈VR.

在VL中存在顶点uL，使得uL∈V2且uL在R中有邻点uR≠v.由归纳假设知，在R中有一条长为2k+t+1-2 的(uR，v)-路 Q.由定理1 知，在 L 中有一条哈密顿(u，uL)-路 P'，则 P=〈u，P'，uL，uR，Q，v 〉为EH(k+1，t)中的一条长为2k+t+2-2 的(u，v)-路.

情形2点u，v都在VL或VR中，不妨设u，v都在VL中.

由归纳假设，在L中有一条长为2k+t+1-2的(u，v)-路T.

断言 2：E(T)∩E3≠Ø.

否则，设 w 和 z是路 T 上的2 个顶点，则 w［s+t：t+1］=z［s+t：t+1］，故|T|≤2t+1＜ 2k+t+1-1，这与T的长度矛盾.因此断言2成立.

设(uL，vL)∈E(T)∩E3.由EH(k+1，t)的定义知，uL和 vL在 R 中都有邻点，分别设为 uR和 vR.它们在R中相邻，由归纳假设知，在R中有一条哈密顿(uR，vR)-路P".设T中的(u，uL)和(vL，v)子路分别为 T1和 T2，则

为EH(k+1，t)中的一条长为2k+t+2-2的(u，v)-路.定理2证毕.

注1EH(1，t)不是哈密顿laceable.

断言3：EH(1，t)中顶点u1=0t+11和u2=10t1之间不存在哈密顿(u1，u2)-路.其中，0k表示有k个0的序列.

否则，设 EH(1，t)存在哈密顿(u1，u2)-路 P，因为 v［0］=0 的点 v在 EH(1，t)中的度是2，且点 u1=0t+11和u2=10t1是路P的端点，所以边集E1⊆E(P).因此，在路P上除去点u1和u2外，v［0］=1的点成对出现，故路 P 上至多含有2t+1-2 个 v［0］=1 的点.在 EH(1，t)中，记 V0={0bt…b11|bj∈{0，1}，j∈［1，t］}，V1={1bt…b11|bj∈{0，1}，j∈［1，t］}，所以由 V0和 V1导出的子图都同构于 Qt.由EH(1，t)的定义，对V0中任意一点u和V1中任意一点v，u和v在EH(1，t)中不相邻.因此，路P上除去u1和u2两点外，至多含有2t-2个V0中的点和2t-2个V1中的点，所以路P上至多含有2t+1-2个v［0］=1的点.与P是哈密顿路矛盾.

［1］徐俊明.组合网络理论［M］.北京：科学出版社，2007.

［2］Loh P K K，Hsu W J，Pan Yi.The exchanged hypercube［J］.Parallel and Distributed Systerms，2005，16(9)：866-874.

［3］Simmons G.Almost all n-dimensional rectangular lattices are Hamilton laceable［J］.Congressus Numerantium，1978(21)：103-108.

［4］Hsieh S Y，Chen G H，Ho C W.Hamiltonian-laceability of star graphs［J］.Networks，2000，36(4)：225-232.

［5］Hsieh S Y，Kwo C N.Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes［J］.Computer Mathematics with Applications，2007，53(7)：1040-1044.

［6］Huang C H.Strongly Hamiltonian laceability of the even k-ary n-cube［J］.Computers and Electrical Engineering，2009，35(5)：659-663.

Hamiltonian laceability and strongly Hamiltonian laceability of exchanged hypercubes

LU Xiaoli，LIU Baodong

(College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

The exchanged hypercube EH(s，t)was a variant of a binary hypercube.It was showed that EH(s，t)(s，t≥2)was Hamiltonian laceable，and，it was also strongly Hamiltonian laceable.

interconnection networks;exchanged hypercube;Hamiltonian laceability;strongly Hamiltonian laceability

O157.5

A

2011-11-23

浙江省重中之重学科开放基金资助项目;浙江师范大学创新团队资助项目

卢晓丽(1986-)，女，山西朔州人，硕士研究生.研究方向：图论.

1001-5051(2012)03-0271-05

(责任编辑 陶立方)

通常用连通的简单图G=(V，E)表示互连网络拓扑结构，其中V和E分别表示图G的点集和边集.用|G|表示图G的点数.本文未定义的记号和术语参阅文献［1］.

由Loh等［2］提出的交换超立方体EH(s，t)(s，t≥1)是由顶点集为V、边集为E组成的图.其中：s，t∈N+;点集 V={as…a1bt…b1c|ai，bj，c∈{0，1}，i∈［1，s］，j∈［1，t］};边集 E 由 3 类互不相交的边集 E1，E2，E3组成：其中：顶点v的右边起第1个二元子序列为第0个分量，第2个二元子序列为第1个分量，依次类推;v［x，y］表示顶点v的从第y个分量到第x分量的长为x-y+1的二元子序列;v［0］表示顶点v的第0个分量的二元子序列;H(x，y)表示2个二元序列x和y之间的Hamming距离，即它们不同的分量的个数.