交換超立方體的哈密頓Laceability和強哈密頓Laceability＊

盧曉麗， 劉保冬

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

交換超立方體的哈密頓Laceability和強哈密頓Laceability＊

盧曉麗， 劉保冬

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

交換超立方體EH(s，t)是超立方體的一個變型.證明了：當(dāng)s，t≥2時，EH(s，t)是哈密頓Laceable，并且也是強哈密頓Laceable.

互連網(wǎng)絡(luò);交換超立方體;哈密頓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］.近年來，學(xué)者研究了許多圖類的哈密頓laceability及強哈密頓 laceability.例如，Hsieh等［5］研究了折疊立方體的強哈密頓 laceability;Huang［6］研究了偶k元n立方體的強哈密頓laceability.本文研究EH(s，t)的哈密頓laceability及強哈密頓laceability.

在給出主要結(jié)果之前，先引入一些有用的引理.

引理1［2］EH(s，t)同構(gòu)于 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)構(gòu)成.為方便定理的證明，引入以下記號.

記 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］}.

根據(jù)EH(k+1，t)的定義，由VL或VR導(dǎo)出的子圖L和R都同構(gòu)于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)的一個自同構(gòu)，使得點u=a2a1b2b1c1同構(gòu)于點00000，故EH(2，2)是點可遷的.

表1構(gòu)造了點00000到與它不同部分的點的哈密頓路.因為EH(2，2)是點可遷的，所以EH(2，2)是哈密頓laceable.表2給出了點00000到與它在同一部分的點的長為30的路.因為EH(2，2)是點可遷的，所以EH(2，2)是強哈密頓laceable.引理3證畢.

定理 1當(dāng) s，t≥2 時，EH(s，t)是哈密頓 laceable.

證明 由引理1知，EH(s，t)同構(gòu)于EH(t，s)，因此只要對s進(jìn)行歸納證明即可.當(dāng)s=2時，由引理 3知，EH(2，2)是哈密頓 laceable.

假設(shè)當(dāng)3≤s≤k時，EH(s，t)是哈密頓 laceable.下證當(dāng) s=k+1 時，EH(k+1，t)是哈密頓 laceable.設(shè)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.由歸納假設(shè)知，在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中，不妨設(shè)u，v都在VL中.

由歸納假設(shè)，在L中有一條哈密頓(u，v)-路P'.

斷言 1：E(P')∩E3≠?.

否則，設(shè) 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成立.

設(shè)(uL，vL)∈E(P')∩E3.由EH(k+1，t)的定義知，uL和 vL在 R 中都有鄰點，分別設(shè)為 uR和 vR.它們在R中相鄰，由歸納假設(shè)知，在R中有一條哈密頓(uR，vR)-路P".設(shè) P'中的(u，uL)和(vL，v)子路分別為 P'1和 P'2，則

表1 點00000到與它在不同部分的點的哈密頓路

表2 點00000到與它在同一部分的點的長為30的路

定理2當(dāng) s，t≥2時，EH(s，t)是強哈密頓 laceable.

證明 由引理1知，EH(s，t)同構(gòu)于EH(t，s)，因此只要對s進(jìn)行歸納證明即可.當(dāng)s=2時，由引理 3知，EH(2，2)是強哈密頓 laceable.假設(shè)當(dāng) 3≤s≤k時，EH(s，t)是強哈密頓 laceable.下證當(dāng) s=k+1時EH(k+1，t)是強哈密頓laceable.

只要證對任意 u，v∈Vi(i∈{1，2})，EH(k+1，t)中存在一條長為 2k+t+2-2 的(u，v)-路即可.不妨設(shè)u，v∈V1.考慮到 EH(k+1，t)=L⊙R，分下面2 種情形來證明.

情形 1u∈VL，v∈VR.

在VL中存在頂點uL，使得uL∈V2且uL在R中有鄰點uR≠v.由歸納假設(shè)知，在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中，不妨設(shè)u，v都在VL中.

由歸納假設(shè)，在L中有一條長為2k+t+1-2的(u，v)-路T.

斷言 2：E(T)∩E3≠?.

否則，設(shè) w 和 z是路 T 上的2 個頂點，則 w［s+t：t+1］=z［s+t：t+1］，故|T|≤2t+1＜ 2k+t+1-1，這與T的長度矛盾.因此斷言2成立.

設(shè)(uL，vL)∈E(T)∩E3.由EH(k+1，t)的定義知，uL和 vL在 R 中都有鄰點，分別設(shè)為 uR和 vR.它們在R中相鄰，由歸納假設(shè)知，在R中有一條哈密頓(uR，vR)-路P".設(shè)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的序列.

否則，設(shè) 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的點成對出現(xiàn)，故路 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導(dǎo)出的子圖都同構(gòu)于 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］徐俊明.組合網(wǎng)絡(luò)理論［M］.北京：科學(xué)出版社，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

浙江省重中之重學(xué)科開放基金資助項目;浙江師范大學(xué)創(chuàng)新團(tuán)隊資助項目

盧曉麗(1986-)，女，山西朔州人，碩士研究生.研究方向：圖論.

1001-5051(2012)03-0271-05

(責(zé)任編輯 陶立方)

通常用連通的簡單圖G=(V，E)表示互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中V和E分別表示圖G的點集和邊集.用|G|表示圖G的點數(shù).本文未定義的記號和術(shù)語參閱文獻(xiàn)［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距離，即它們不同的分量的個數(shù).