边故障k元n立方体的超级哈密顿交织性

张淑蓉，王世英，董操

山西大学数学科学学院，太原 030006

边故障k元n立方体的超级哈密顿交织性

张淑蓉，王世英，董操

山西大学数学科学学院，太原 030006

k元n立方体（记为）是优于超立方体的可进行高效信息传输的互连网络之一。是一个二部图当且仅当k为偶数。令G[V0，V1]是一个二部图，若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路，且（2）对于任意一点v∈Vi，其中i∈{0，1}，V1-i中任意一对顶点可以被G[V0，V1]-v中的一条哈密顿路相连，则图G[V0，V1]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的，所以研究网络的容错性就尤为重要。针对含有边故障的，其中k≥4是偶数且n≥2，证明了当其故障边数至多为2n-3时，该故障是超级哈密顿交织图，且故障边数目的上界2n-3是最优的。

互连网络；超级哈密顿交织性；k元n立方体

1 引言和基本概念

随着计算机应用的不断深入，迫切需要速度更快，性能更高的计算机系统，进而开辟了并行和分布式系统的研究领域。系统中元件之间的连接模式称为该系统的互连网络，或者简称为网络。毫无疑问，并行和分布式系统功能的实现在很大程度上依赖于该系统的互连网络结构。k元n立方体是最重要的互连网络之一[1-4]。它具有许多优良性质，如易运行，低延迟和高带宽。正是这些优良的性质，k元n立方体受到了广泛关注，并且大量的并行和分布式系统都是基于k元n立方体来形成其连接模式，如iWarp[5]，J-machine[6]和IBM Blue Gene/L[7]。

互连网络可以看成一个图G=(V(G)，E(G))，其中V(G)和E(G)分别表示G的顶点集和边集。图的顶点表示系统中的元件，图的边表示元件之间的物理连线。在G中，顶点u的所有邻点组成的集合称为u的邻域，记作NG(u)。若G的顶点可以被划分为两个集合V0和V1，使得每条边的端点一个在V0中，另一个在V1中，则称图是二部图，这样的一个分划(V0，V1)被称为是图G的一个二分划，V0和V1被称为是图的两个部。若二部图中任意一对分别在不同部的顶点之间存在一条哈密顿路，则称该图是哈密顿交织图[8]。

设G是具有二分划(V0，V1)的哈密顿交织图。若Vi中任意一对顶点可以被G中的一条长度为|V(G)|-2的路相连，则图G被称为是强哈密顿交织图[9]。对于任意一点v∈Vi，其中i∈{0，1}，V1-i中任意一对顶点可以被G-v中的一条哈密顿路相连，则图G被称为是超级哈密顿交织图[10]。

由以上定义可以看出，若G是超级哈密顿交织图，则G一定是强哈密顿交织图。

在实际应用中，网络中的元件或连线也可能发生故障从而影响到网络的正常运行，所以研究故障网络的（强或超级）哈密顿交织性具有重要的意义[11-13]。

Huang在2009年[9]已经证明了当k为偶数时，不含故障边的k元n立方体是强哈密顿交织图。而本文是在文献[9]的基础上所做的进一步研究，并且证明了：至多含有2n-3条故障边的k元n立方体（k为偶数）是超级哈密顿交织图，可见该结果推广并涵盖了文献[9]的主要结论。

定义1（m-边容错（超级）哈密顿交织图）设G是二部图，F(|F|≤m)是G的故障边集合。若G为（超级）哈密顿交织图且G-F仍为（超级）哈密顿交织图，则称G是m-边容错（超级）哈密顿交织图。

定义2（k元n立方体）k元n立方体，记为(k≥1， n≥1)，是一个具有kn个顶点的图，每个顶点可以标记为u=un-1un-2…u0，其中ui∈{0，1，…，k-1}，0≤i≤n-1。两个顶点u=un-1un-2…u0和v=vn-1vn-2…v0相邻当且仅当存在一个整数j∈{0，1，…，n-1}，使得uj=vj±1 (mod k)且对每个i∈{0，1，…，n-1}{j}都有ui=vi。这样的边uv被称为是一条j维边。为书写方便，在本文中遇到类似情况时省略“(mod k)”。

取定一个正整数j∈{0，1，…，n-1}。删除所有的j维边便可以沿第j维将(k≥2)划分为k个不相交的子立方，依次记为：0]，[1]，…，[k-1]（在不引起歧义的情况下，简记为Q[0]，Q[1]，…，Q[k-1]，如图1）。显然对每一个0≤i≤k-1，Q[i]均与同构。在该中任取一点u=uu…uuu…u，不失一般n-1n-2j+1jj-10性，假设u∈V(Q[i])，其中0≤i≤k-1。记Q[i′]中的顶点v=un-1un-2…uj+1vjuj-1…u0为ni′(u)，其中vj≠uj。可以看出ni′(u)和u相邻当且仅当i′=i±1。

图1 将划分为Q[0]，Q[1]，…，Q[k-1]

图3 的子图Row[0:3]

图2 的子图Row[0:2]

2 主要结论

首先给出对主要结论证明有用的一些引理。

引理2.1[14]在Row[0:p]中任取3个不同的顶点s，t和x，其中1≤p≤k-1。若δ(x，s)=1且δ(s，t)=0，则Row[0:p]-x中存在一条哈密顿st-路。

引理2.2[15]设n≥2是整数，k≥4是偶数。在中任取两个相邻顶点s*和t*，则-{u*，v*}是哈密顿交织图。

引理2.3[16]若n≥2是整数，k≥4是偶数，则是(2n-2)-边容错哈密顿交织图。

图4 情形1.1.1中哈密顿路的构造方法演示

图5 情形1.2.1中哈密顿路的构造方法演示

图6 情形2中哈密顿路的构造方法演示

3 结束语

本文主要对含有故障边的k元n立方体（k≥4为偶数）的超级哈密顿交织性进行了研究。证明了若该k元n立方体中的故障边集F满足|F|≤2n-3，则-F是超级哈密顿交织图。这一结果表明，就超级哈密顿交织性来说，k元n立方体（k≥4为偶数）具有良好的故障容错能力，这一结果对于建立k元n立方体（k≥4为偶数）环境下的T比特路由器是不无裨益的。

[1]Bose B，Broeg B，Younggeun K，et al.Lee distance and topological properties of k-ary n-cubes[J].IEEE Transactions on Computers，1995，44（8）：1021-1030.

[2]Dally W J.Performance analysis of k-ary n-cube interconnection networks[J].IEEE Transactions on Computers，1990，39（6）：775-785.

[3]Ghozati S A，Wasserman H C.The k-ary n-cube network：modeling，topological properties and routing strategies[J]. Computers and Electrical Engineering，1999，25（3）：155-168.

[4]Hsieh S Y，Chang Y H.Extraconnectivity of k-ary n-cube networks[J].Theoretical Computer Science，2012，443（20）：63-69.

[5]Peterson C，Sutton J，Wiley P.iWarp：a 100-MOPS，LIW microprocessor for multicomputers[J].IEEE Micro，1991，11（3）：26-29，81-87.

[6]Noakes M，Dally W J.System design of the J-machine[C]// 6th MIT Conference on Advanced Research in VLSI，1990：179-194.

[7]Adiga N R，Blumrich M A，Chen D，et al.Blue Gene/L torus interconnection network[J].IBM Journal of Research and Development，2005，49（2）：265-276.

[8]Wong S A.Hamiltonian cycles and paths in buttery graphs[J]. Networks，1995，26（3）：145-150.

[9]Huang C H.Strongly Hamiltonian laceability of the even k-ary n-cube[J].Computers and Electrical Engineering，2009，35（5）：659-663.

[10]Lewinter M，Widulski W.Hyper-Hamilton laceable and caterpillar-spannable product graphs[J].Computers and Mathematics with Applications，1997，34（11）：99-104.

[11]Li T K，Tan J J M，Hsu L H.Hyper hamiltonian laceability on edge fault star graph[J].Information Sciences，2004，165（1/2）：59-71.

[12]Tsai C H，Tan J J M，Liang T，et al.Fault-tolerant Hamiltonian laceability of hypercubes[J].Information Processing Letters，2002，83（6）：301-306.

[13]Araki T，Kikuchi Y.Hamiltonian laceability of bubblesort graphs with edge faults[J].Information Sciences，2007，177（13）：2679-2691.

[14]Kim H C，Park J H.Fault hamiltonicity of two-dimensional torus networks[C]//Workshop on Algorithms and Computation，Tokyo，Japan，2000：110-117.

[15]Wang Shiying，Zhang Shurong.Embedding hamiltonian paths in k-ary n-cubes with conditional edge faults[J]. Theoretical Computer Science，2011，412（46）：6570-6584.

[16]Stewart I A，Xiang Yonghong.Embedding long paths in k-ary n-cubes with faulty nodes and links[J].IEEE Transactions on Parallel and Distributed Systems，2008，19（8）：1071-1085.

ZHANG Shurong,WANG Shiying,DONG Cao

School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China

Thek-aryn-cube,denoted by,as one of the most efficient interconnection networks for information

transportation,has been shown as an alternative to the hypercube.Ais bipartite if and only ifkis even.A bipartite graphG[V0，V1]is called hyper hamiltonian laceable if（1）it has a hamiltonian path between any pair of vertices in different parts,and（2）for any vertexv∈Vi,there is a hamiltonian path ofG[V0，V1]-vbetween any two vertices inV1-i,where i∈{0，1}.Since edge faults may occur after a network is activated,it is important to solve problems in faulty networks. This paper addresses the faultywith evenk≥4andn≥2,and proves that thewith at most2n-3faulty edges is hyper hamiltonian laceable.This result is optimal to the number of edge faults tolerated.

interconnection networks;hyper hamiltonian laceability;k-aryn-cubes

A

O157.5

10.3778/j.issn.1002-8331.1212-0216

ZHANG Shurong,WANG Shiying,DONG Cao.Hyper hamiltonian laceability of k-ary n-cubes with edge faults. Computer Engineering and Applications,2014,50（21）：39-43.

国家自然科学基金（No.61070229）；教育部高等学校博士点专项基金（No.20111401110005）。

张淑蓉（1984—），女，博士研究生，研究领域为图论及其应用；王世英（1961—），男，博士，教授，研究领域为图论及其应用；董操（1983—），男，硕士研究生，研究领域为图论及其应用。E-mail：zhangsr@sxu.edu.cn

2012-12-18

2013-07-09

1002-8331（2014）21-0039-05

CNKI出版日期：2013-08-05，http://www.cnki.net/kcms/detail/11.2127.TP.20130805.0943.004.html