Hamiltonian connectivity of the WK-recursive network with faulty nodes

A graph G is said to be Hamiltonian-connected if there is a Hamiltonian path between every two distinct nodes of G. Let F denote the set of faulty nodes of G. Then, G is |F|-node Hamiltonian-connected if G-F is Hamiltonian-connected. We use K(d,t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph. Compared with other networks, it is rather difficult to construct a Hamiltonian path between two arbitrary nodes in a faulty WK-recursive network. In this paper, we show that K(d,t) is (d-4)-node Hamiltonian-connected. Since the connectivity of K(d,t) is d-1, the result is optimal in the worst case.     

Conditional edge-fault Hamiltonicity of augmented cubes

The augmented cube is a variation of hypercubes, it possesses many superior properties. In this paper, we show that, for any n-dimensional augmented cube (n?3) with faulty edges up to 4n-8 in which each vertex is incident to at least two fault-free edges, there exists a fault-free Hamiltonian cycle. Our result is optimal with respect to the number of faulty edges tolerated.     

Pancyclicity and bipancyclicity of conditional faulty folded hypercubes

A graph is said to be pancyclic if it contains cycles of every length from its girth to its order inclusive; and a bipartite graph is said to be bipancyclic if it contains cycles of every even length from its girth to its order. The pancyclicity or the bipancyclicity of a given network is an important factor in determining whether the network’s topology can simulate rings of various lengths. An n-dimensional folded hypercube FQ_n is an attractive variant of an n-dimensional hypercube Q_n that is obtained by establishing some extra edges between the vertices of Q_n. FQ_n for any odd n is known to be bipartite. In this paper, we explore the pancyclicity and bipancyclicity of FQ_n. For any FQ_n (n ? 2) with at most 2n − 3 faulty edges, where each vertex is incident to at least two fault-free edges, we prove that there exists a fault-free cycle of every even length from 4 to 2ⁿ; and when n ? 2 is even, we prove there also exists a fault-free cycle of every odd length from n + 1 to 2ⁿ − 1. The result is optimal with respect to the number of faulty edges tolerated.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

Hamiltonian properties on the class of hypercube-like networks

Hamiltonian properties of hypercube variants are explored. Variations of the hypercube networks have been proposed by several researchers. In this paper, we show that all hypercube variants are hamiltonian-connected or hamiltonian-laceable. And we also show that these graphs are bipancyclic.     

具有大量错误结点的超立方体网络中的单播路由算法的设计与分析

本文讨论具有大量错误结点的超立方体网络中的单播路由算法，假定Hn是一个局部3－维子立方体连通的n-维超立方体网络并且每一个基本的3－维子立方体中分别最多有1个和2个错误结点，本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约1．5倍和2倍海明距离的次优路径，我们提出的单播路由算法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。     

Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks

We propose a new family of communication architectures called ‘biswapped networks’. Given any n-node basis network Ω, the associated biswapped network Bsw(Ω) is built of 2n copies of Ω, using a simple rule for connectivity that ensures desirable attributes, including regularity, modularity, fault tolerance, and algorithmic efficiency. In particular, if Ω is a Cayley digraph, then so is Bsw(Ω). Our biswapped connectivity provides a systematic scheme for synthesizing large, scalable, modular, and robust parallel architectures. Furthermore, many desirable attributes of the underlying basis network Ω are preserved, as the Bsw(Ω) parameters are related to the corresponding parameters of Ω. We obtain a number of results on internode distances, Hamiltonian cycles, optimal routing, and node-disjoint paths for Bsw(Ω). We explore the relations between biswapped and swapped or optical transpose interconnection system (OTIS) networks, which may use a mix of electronic and optical links. In particular, we demonstrate that the biswapped connectivity removes an inherent asymmetry of swapped/OTIS networks, as well as the attendant complications in analyses and applications. Finally, we show that biswapped networks are complementary to, and offer advantages over, well-known and widely used interconnection architectures for parallel processing.