Abstract The alternating group graph, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. Previously, the alternating group graph was shown to be pancyclic, i.e., containing cycles of all possible lengths. In this article, we further show that the alternating group graph remains pancyclic, even if there are up to 2n − 6 edge faults, where n ≥ 3 is the dimension of the alternating group graph. The result is optimal with respect to the number of edge faults tolerated. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

The n-dimensional twisted cube, denoted by TQn, a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each vertex is incident with at least two fault-free links, we show that TQncan tolerate up to 2n - 5 edge faults, while retaining a fault-free Hamiltonian cycle. The result is optimal with respect to the number of edge faults tolerated

The star graph possesses many nice topological properties. In this study, we show that for any n dimensional star graph (n ges 4) with les 2n - 7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compare with the corresponding study in hypercube, our method is rather succinct

Much research on the WK-recursive network has been published during the past few years due to its many favorable properties. We use K(d1t) to denote a WK-recursive network of level t, each of whose basic modules is a d-node complete graph, where d <> 1 and t ges 1. Let F denote the set of faulty nodes in K(d, t). In this study, we show that K(d, t) - F is Hamiltonian connected when | F| les d - 4. Therefore, K(d, t) - F can embed the longest linear array between any two distinct nodes with dilation, congestion, load, and expansion all equal to one. In addition, since the connectivity of K(d, t) is d - 1, the result is optimal

The crossed cube, which is a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, assuming that each node is incident with at least two fault-free links, we show that an n-dimensional crossed cube can tolerate up to 2n - 5 link faults, while retaining a fault-free Hamiltonian cycle. The result is optimal with respect to the number of link faults tolerated. We also verify that the assumption is practically meaningful by evaluating its probability to occur, which is very close to 1, even if n is small

Recently, the WK-recursive network has received much attention due to its many favorable properties such as a high degree of scalability. By K(d,t), we denote the WK-recursive network of level t, each of whose basic modules is a d-node complete graph, where d>1 and t/spl ges/1. In this paper, we first show that K(d,t) is Hamiltonian-connected, where d/spl ges/4. A network is Hamiltonian-connected if it contains a Hamiltonian path between every two distinct nodes. In other words, a Hamiltonian-connected network can embed the longest linear array between any two distinct nodes with dilation, congestion, load, and expansion all equal to one. Then, we construct fault-free Hamiltonian cycles in K(d,t) with at most d-3 faulty nodes, where d/spl ges/4. Since the connectivity of K(d,t) is d-1, the result is optimal.

Abstract A hierarchical cubic network was proposed as an alternative to the hypercube. By HCN(n), we denote the hierarchical cubic network that contains 2nn‐dimensional hypercubes. In this paper, using Gray codes, we construct fault‐free Hamiltonian cycles in an HCN(n) withn− 1 link faults. Since the HCN(n) is regular of degreen+ 1, the result is optimal. We also construct longest fault‐free cycles of length 22n− 1 in an HCN(n) with a one‐node fault and fault‐free cycles of length at least 22n− 2fin an HCN(n) withf‐node faults, where 22nis the number of nodes in the HCN(n),f≤n− 1 ifn= 3 or 4 andf≤nifn≥ 5. Our results can be applied to the hierarchical folded‐hypercube network as well. © 2003 Wiley Periodicals, Inc.

The hypercube is one of the most versatile and efficient interconnection networks yet discovered for parallel computation. We show that a fault-free cycle of length of at least 2n - 2f can be embedded in an n dimensional hypercube with f faulty nodes, where n /spl ges/ 3 and 1 /spl les/ f /spl les/ 2n - 4. The best known results thus far can tolerate only n - 1 faulty nodes.

Abstract Ann‐dimensional hierarchical cubic network [denoted by HCN(n)] contains 2nn‐dimensional hypercubes. The diameter of the HCN(n), which is equal ton+ ⌊(n+ 1)/3⌋ + 1, is about two‐thirds the diameter of a comparable hypercube, even though it uses about half as many links per node. In this paper, a maximal number of node‐disjoint paths are constructed between every two distinct nodes of the HCN(n). Their maximal length is bounded above byn+ ⌊n/3⌋ + 4, which is nearly optimal. The (n+ 1)‐wide diameter andn‐fault diameter of the HCN(n) are shown to ben+ ⌊n/3⌋ + 3 orn+ ⌊n/3⌋ + 4, which are about two‐thirds those of a comparable hypercube. Our results reveal that the HCN(n) has a smaller wide diameter and fault diameter than those of a comparable hypercube. © 2002 Wiley Periodicals, Inc.

An n-dimensional hierarchical cubic network (denoted by HCN(n)) contains 2/sup n/ n-dimensional hypercubes. The diameter of an HCN(n), which is equal to n+[(n+1)/3]+1, is about two-thirds the diameter of a comparable hypercube, although it uses about half as many links per node. In this paper, a maximal number of node-disjoint paths are constructed between every two distinct nodes of an HCN(n). Their maximal length has an upper bound of n+[n/3]+4, which is nearly optimal. The (n+1)-wide diameter and n-fault diameter of an HCN(n) are shown to be n+[n/3]+3 or n+[n/3]+4, which are about two-thirds those of a comparable hypercube. Our results reveal that an HCN(n) has shorter node-disjoint paths, wide diameter, and fault diameter than a comparable hypercube.

This paper introduces a pancyclic recursive topology, named the hypercomplete, for building large-scale distributed multicomputer systems. The hypercomplete is maximally fault-tolerant and has a logarithmic diameter. In addition to being pancyclic, the hypercomplete is Hamiltonian-connected. Consequently, the hypercomplete can embed rings of all possible lengths and a longest linear array between arbitrary two nodes. Besides, the hypercomplete can embed tori and trees with constant dilation and constant congestion. Some algorithms are developed for the hypercomplete. An algorithm is proposed to determine a shortest path between arbitrary two nodes. A broadcasting algorithm without redundant messages is proposed, whose resulting spanning tree has its height bounded above by the diameter. The class of ascend/descend algorithms can be executed efficiently. © 2000 John Wiley & Sons, Inc.