Cycles passing through a prescribed path in a hypercube with faulty edges

Let Qn denote an n-dimensional hypercube with n?2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if |F|?h−2. In this paper, we show that if 1?h?2n−3 and |F|?n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |F∩E(Qh)|?h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1?h?2n−3.     

Hamiltonian paths and cycles passing through a prescribed path in hypercubes

Assume that P is any path in a bipartite graph G of length k with 2?k?h, G is said to be h-path bipancyclic if there exists a cycle C in G of every even length from 2k to |V(G)| such that P lies in C. In this paper, the following result is obtained: The n-dimensional hypercube Qn with n?3 is (2n−3)-path bipancyclic but is not (2n−2)-path bipancyclic, moreover, a path P of length k with 2?k?2n−3 lies in a cycle of length 2k−2 if and only if P contains two edges of the same dimension. In order to prove the above result we first show that any path of length at most 2n−1 is a subpath of a Hamiltonian path in Qn with n?2, moreover, the upper bound 2n−1 is sharp when n?4.     

Embedding a long fault-free cycle in a crossed cube with more faulty nodes

The crossed cube is an important variant of the most popular hypercube network for parallel computing. In this paper, we consider the problem of embedding a long fault-free cycle in a crossed cube with more faulty nodes. We prove that for n?5 and f?2n−7, a fault-free cycle of length at least n²−f−(n−5) can be embedded in an n-dimensional crossed cube with f faulty nodes. Our work extends some previously known results in the sense of the maximum number of faulty nodes tolerable in a crossed cube.     

Hamiltonian properties of twisted hypercube-like networks with more faulty elements

Twisted hypercube-like networks (THLNs) are a large class of network topologies, which subsume some well-known hypercube variants. This paper is concerned with the longest cycle in an n-dimensional (n-D) THLN with up to 2n−9 faulty elements. Let G be an n-D THLN, n≥7. Let F be a subset of V(G)?E(G), |F|≤2n−9. We prove that G−F contains a Hamiltonian cycle if δ(G−F)≥2, and G−F contains a near Hamiltonian cycle if δ(G−F)≤1. Our work extends some previously known results.     

Embedding a fault-free hamiltonian cycle in a class of faulty generalized honeycomb tori

Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m ? 2 and d ? 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs.     

A further result on fault-free cycles in faulty folded hypercubes

Folded hypercube is a well-known variation of the hypercube structure and can be constructed from a hypercube by adding a link to every pair of nodes with complementary addresses. Let FFv (respectively, FFe) be the set of faulty nodes (respectively, faulty links) in an n-dimensional folded hypercube FQn. Fu has showed that FQn−FFv−FFe for n?3 contains a fault-free cycle of length at least n²−2|FFv| if |FFv|+|FFe|?2n−4 and |FFe|?n−1. In this paper, we further consider the constraints |FFv|+|FFe|?2n−4 and |FFe|?n that were not covered by Fu's result. We obtain the same lower bound of the longest fault-free cycle length, n²−2|FFv|, under the constraints that (1) |FFv|+|FFe|?2n−4 and (2) every node in FQn is incident to at least two fault-free links.     

On the maximal connected component of hypercube with faulty vertices

In evaluating an interconnection network, it is indispensable to estimate the size of the maximal connected components of the underlying graph when the network begins to lose processors. Hypercube is one of the most popular interconnection networks. This article addresses the maximal connected components of an n-dimensional cube with faulty processors. We first prove that an n-cube with a set F of at most 2n???3 failing processors has a component of size ≥2 ⁿ ???|F|???1. We then prove that an n-cube with a set F of at most 3n???6 missing processors has a component of size ≥2 ⁿ ???|F|???2.     

A note on cycle embedding in hypercubes with faulty vertices

Let fv denote the number of faulty vertices in an n-dimensional hypercube. This note shows that a fault-free cycle of length of at least n²−2fv can be embedded in an n-dimensional hypercube with fv=2n−3 and n?5. This result not only enhances the previously best known result, and also answers a question in [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832].     

On the maximal connected component of hypercube with faulty vertices (II)

In evaluating the fault tolerance of an interconnection network, it is essential to estimate the size of a maximal connected component of the network at the presence of faulty processors. Hypercube is one of the most popular interconnection networks. In this paper, we prove that for n?≥?6, an n-dimensional cube with a set F of at most (4n???10) failing processors has a component of size ≥2″???|F|???3. This result demonstrates the superiority of hypercube in terms of the fault tolerance.     

On embedding cycles into faulty dual-cubes

A dual-cube uses low-dimensional hypercubes as basic components such that keeps the main desired properties of the hypercube. Each hypercube component is referred as a cluster. A (n+1)-connected dual-cube DC(n) has ²2n+1 nodes and the number of nodes in a cluster is n². There are two classes with each class consisting of n² clusters. Each node is incident with exactly n+1 links where n is the degree of a cluster, one more link is used for connecting to a node in another cluster. In this paper, we show that every node of DC(n) lies on a cycle of every even length from 4 to ²2n+1 inclusive for n?3, that is, DC(n) is node-bipancyclic for n?3. Furthermore, we show that DC(n), n?3, is bipancyclic even if it has up to n−1 edge faults. The result is optimal with respect to the number of edge faults tolerant.     

The fastcube: a variation on hypercube topology with lower diameter

This paper presents a class of n-dimensional interconnection topologies with N=2ⁿ nodes which we refer to as n-fastcubes. The node degree of the n-fastcube is n and its diameter is ⌈(n+1)/2⌉, which is substantially smaller than that of the same size hypercube. Topological properties as well as several routing algorithms for fastcubes are developed. In addition, a new methodology for the design and analysis of fastcubes is employed. This methodology is based on modeling interconnection networks as finite state automata. The inputs to these particular automata are routing sequences. The routing and embedding algorithms developed in this paper produce routing sequences. The main characteristic of routing sequences is their node independence. A node independent routing sequence, p(H), produces a path between any pair of nodes with the Hamming distance of H. Thus, these sequences can be used, without modification, at any node to establish paths in a fastcube.     

Generalized honeycomb torus is Hamiltonian

Generalized honeycomb torus is a candidate for interconnection network architectures, which includes honeycomb torus, honeycomb rectangular torus, and honeycomb parallelogramic torus as special cases. Existence of Hamiltonian cycle is a basic requirement for interconnection networks since it helps map a “token ring” parallel algorithm onto the associated network in an efficient way. Cho and Hsu [Inform. Process. Lett. 86 (4) (2003) 185-190] speculated that every generalized honeycomb torus is Hamiltonian. In this paper, we have proved this conjecture.     

Cycles embedding in hypercubes with node failures

The hypercube has been widely used as the interconnection network in parallel computers. The n-dimensional hypercube Qn is a graph having n² vertices each labeled with a distinct n-bit binary strings. Two vertices are linked by an edge if and only if their addresses differ exactly in the one bit position. Let fv denote the number of faulty vertices in Qn. For n?3, in this paper, we prove that every fault-free edge and fault-free vertex of Qn lies on a fault-free cycle of every even length from 4 to n²−2fv inclusive even if fv?n−2. Our results are optimal.     

Fault-free Hamiltonian cycles in crossed cubes with conditional link faults

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 contains a fault-free Hamiltonian cycle, even if there are up to 2n − 5 link faults. 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 occurrence probability, which is very close to 1.     

Finding cycles in hierarchical hypercube networks

The hierarchical hypercube network, which was proposed as an alternative to the hypercube, is suitable for building a large-scale multiprocessor system. A bipartite graph G=(V,E) is bipancyclic if it contains cycles of all even lengths ranging from 4 to |V|. In this paper, we show that the hierarchical hypercube network is bipancyclic.     

Fault-free mutually independent Hamiltonian cycles of faulty star graphs

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG _n denote an n-dimensional star network in which f≤n?3 edges may fail accidentally. We show that there exist (n?2?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n∈{3, 4}, and there exist (n?1?f)-mutually independent Hamiltonian cycles rooted at any vertex in SG _n if n≥5.     

Longest fault-free paths in hypercubes with vertex faults

The hypercube is one of the most versatile and efficient interconnection networks (networks for short) so far discovered for parallel computation. Let f denote the number of faulty vertices in an n-cube. This study demonstrates that when f ? n − 2, the n-cube contains a fault-free path with length at least 2ⁿ − 2f − 1 (or 2ⁿ − 2f − 2) between two arbitrary vertices of odd (or even) distance. Since an n-cube is a bipartite graph with two partite sets of equal size, the path is longest in the worst-case. Furthermore, since the connectivity of an n-cube is n, the n-cube cannot tolerate n − 1 faulty vertices. Hence, our result is optimal.