交換超立方體的哈密頓Laceability和強(qiáng)哈密頓Laceability＊

盧曉麗， 劉保冬

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

交換超立方體的哈密頓Laceability和強(qiáng)哈密頓Laceability＊

盧曉麗， 劉保冬

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

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

互連網(wǎng)絡(luò);交換超立方體;哈密頓Laceability;強(qiáng)哈密頓Laceability

由EH(s，t)的定義知，它是具有2s+t+1個(gè)頂點(diǎn)、(s+t+2)2s+t-1條邊的二部圖.將二部圖記為G=(V1，V2;E)，其中 V1和 V2是圖的頂點(diǎn)集合的二部劃分.用 P=〈u，P1，s，t，P2，v 〉表示一條以 u，v為端點(diǎn)的(u，v)-路，其中P1和P2分別表示路P中u到s和t到v的子路.若V(P)=V(G)，則稱路P是哈密頓路.在二部圖中，若對(duì)不同部分的任意2個(gè)頂點(diǎn)u∈V1，v∈V2，圖中存在哈密頓(u，v)-路，則稱二部圖是哈密頓 laceable［3］.若二部圖是哈密頓 laceable，且對(duì)同一部分的任意 2 個(gè)點(diǎn) u，v∈Vi，i∈{1，2}，圖中存在一條長(zhǎng)為|G|-2的(u，v)-路，則稱二部圖是強(qiáng)哈密頓laceable［4］.近年來(lái)，學(xué)者研究了許多圖類的哈密頓laceability及強(qiáng)哈密頓 laceability.例如，Hsieh等［5］研究了折疊立方體的強(qiáng)哈密頓 laceability;Huang［6］研究了偶k元n立方體的強(qiáng)哈密頓laceability.本文研究EH(s，t)的哈密頓laceability及強(qiáng)哈密頓laceability.

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

引理1［2］EH(s，t)同構(gòu)于 EH(t，s).

引理2［2］EH(s，t)可分解為 2 個(gè) EH(s-1，t)或 2 個(gè) EH(s，t-1).

由引理2知，EH(k+1，t)可由2個(gè)EH(k，t)構(gòu)成.為方便定理的證明，引入以下記號(hào).

記 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和強(qiáng)哈密頓laceable.

證明 先證 EH(2，2)是點(diǎn)可遷的.對(duì)點(diǎn) u=a2a1b2b1c1∈V(EH(2，2))，令 σ(x2x1y2y1c)=(x2⊕a2)(x1⊕a1)(y2⊕b2)(y1⊕b1)(c⊕c1)，其中⊕表示模2加法.易證σ是EH(2，2)的一個(gè)自同構(gòu)，使得點(diǎn)u=a2a1b2b1c1同構(gòu)于點(diǎn)00000，故EH(2，2)是點(diǎn)可遷的.

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

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

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

假設(shè)當(dāng)3≤s≤k時(shí)，EH(s，t)是哈密頓 laceable.下證當(dāng) s=k+1 時(shí)，EH(k+1，t)是哈密頓 laceable.設(shè)V1和V2是EH(k+1，t)的頂點(diǎn)集合的二部劃分.要證EH(k+1，t)是哈密頓laceable，只要證任意u∈V1，v∈V2，EH(k+1，t)中存在一條哈密頓(u，v)-路即可.

考慮到EH(k+1，t)=L⊙R，分下面2種情形來(lái)證明.

情形 1u∈VL，v∈VR.

在VL中存在頂點(diǎn)uL，使得uL∈V2且uL在R中有鄰點(diǎn)uR.由歸納假設(shè)知，在L中有一條哈密頓(u，uL)-路 P'，在 R 中有一條哈密頓(uR，v)-路 P"，則 P=〈u，P'，uL，uR，P"，v 〉為 EH(k+1，t)中的一條哈密頓(u，v)-路.

情形2點(diǎn)u，v都在VL或VR中，不妨設(shè)u，v都在VL中.

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

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

否則，設(shè) w 和 z是路 P'上的2 個(gè)頂點(diǎn)，則 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 中都有鄰點(diǎn)，分別設(shè)為 uR和 vR.它們?cè)赗中相鄰，由歸納假設(shè)知，在R中有一條哈密頓(uR，vR)-路P".設(shè) P'中的(u，uL)和(vL，v)子路分別為 P'1和 P'2，則

表1 點(diǎn)00000到與它在不同部分的點(diǎn)的哈密頓路

表2 點(diǎn)00000到與它在同一部分的點(diǎn)的長(zhǎng)為30的路

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

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

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

情形 1u∈VL，v∈VR.

在VL中存在頂點(diǎn)uL，使得uL∈V2且uL在R中有鄰點(diǎn)uR≠v.由歸納假設(shè)知，在R中有一條長(zhǎng)為2k+t+1-2 的(uR，v)-路 Q.由定理1 知，在 L 中有一條哈密頓(u，uL)-路 P'，則 P=〈u，P'，uL，uR，Q，v 〉為EH(k+1，t)中的一條長(zhǎng)為2k+t+2-2 的(u，v)-路.

情形2點(diǎn)u，v都在VL或VR中，不妨設(shè)u，v都在VL中.

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

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

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

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

為EH(k+1，t)中的一條長(zhǎng)為2k+t+2-2的(u，v)-路.定理2證畢.

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

斷言3：EH(1，t)中頂點(diǎn)u1=0t+11和u2=10t1之間不存在哈密頓(u1，u2)-路.其中，0k表示有k個(gè)0的序列.

否則，設(shè) EH(1，t)存在哈密頓(u1，u2)-路 P，因?yàn)?v［0］=0 的點(diǎn) v在 EH(1，t)中的度是2，且點(diǎn) u1=0t+11和u2=10t1是路P的端點(diǎn)，所以邊集E1?E(P).因此，在路P上除去點(diǎn)u1和u2外，v［0］=1的點(diǎn)成對(duì)出現(xiàn)，故路 P 上至多含有2t+1-2 個(gè) v［0］=1 的點(diǎn).在 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)的定義，對(duì)V0中任意一點(diǎn)u和V1中任意一點(diǎn)v，u和v在EH(1，t)中不相鄰.因此，路P上除去u1和u2兩點(diǎn)外，至多含有2t-2個(gè)V0中的點(diǎn)和2t-2個(gè)V1中的點(diǎn)，所以路P上至多含有2t+1-2個(gè)v［0］=1的點(diǎn).與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é)科開放基金資助項(xiàng)目;浙江師范大學(xué)創(chuàng)新團(tuán)隊(duì)資助項(xiàng)目

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

1001-5051(2012)03-0271-05

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

通常用連通的簡(jiǎn)單圖G=(V，E)表示互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中V和E分別表示圖G的點(diǎn)集和邊集.用|G|表示圖G的點(diǎn)數(shù).本文未定義的記號(hào)和術(shù)語(yǔ)參閱文獻(xiàn)［1］.

由Loh等［2］提出的交換超立方體EH(s，t)(s，t≥1)是由頂點(diǎn)集為V、邊集為E組成的圖.其中：s，t∈N+;點(diǎn)集 V={as…a1bt…b1c|ai，bj，c∈{0，1}，i∈［1，s］，j∈［1，t］};邊集 E 由 3 類互不相交的邊集 E1，E2，E3組成：其中：頂點(diǎn)v的右邊起第1個(gè)二元子序列為第0個(gè)分量，第2個(gè)二元子序列為第1個(gè)分量，依次類推;v［x，y］表示頂點(diǎn)v的從第y個(gè)分量到第x分量的長(zhǎng)為x-y+1的二元子序列;v［0］表示頂點(diǎn)v的第0個(gè)分量的二元子序列;H(x，y)表示2個(gè)二元序列x和y之間的Hamming距離，即它們不同的分量的個(gè)數(shù).