卢晓丽， 刘保冬

(浙江师范大学数理与信息工程学院，浙江金华 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.表……