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.     

Highly fault-tolerant cycle embeddings of hypercubes

The hypercube Q_n is one of the most popular networks. In this paper, we first prove that the n-dimensional hypercube is 2n − 5 conditional fault-bipancyclic. That is, an injured hypercube with up to 2n − 5 faulty links has a cycle of length l for every even 4 ⩽ l ⩽ 2ⁿ when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to 2n − 3 faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to 2n − 5 faulty links under all possible fault distributions.     

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.     

Long paths and cycles in hypercubes with faulty vertices

A fault-free path in the n-dimensional hypercube Q_n with f faulty vertices is said to be long if it has length at least 2ⁿ-2f-2. Similarly, a fault-free cycle in Q_n is long if it has length at least 2ⁿ-2f. If all faulty vertices are from the same bipartite class of Q_n, such length is the best possible. We show that for every set of at most 2n-4 faulty vertices in Q_n and every two fault-free vertices u and v satisfying a simple necessary condition on neighbors of u and v, there exists a long fault-free path between u and v. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n²/10+n/2+1 faulty vertices in Q_n where n?15 that Q_n has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.     

Fault-tolerant hamiltonian laceability of hypercubes

It is known that every hypercube Q_n is a bipartite graph. Assume that n?2 and F is a subset of edges with |F|?n−2. We prove that there exists a hamiltonian path in Q_n−F between any two vertices of different partite sets. Moreover, there exists a path of length 2ⁿ−2 between any two vertices of the same partite set. Assume that n?3 and F is a subset of edges with |F|?n−3. We prove that there exists a hamiltonian path in Q_n−{v}−F between any two vertices in the partite set without v. Furthermore, all bounds are tight.     

Fault-Tolerant Hamiltonicity of Twisted Cubes

The twisted cube TQ_n, is derived by changing some connection of hypercube Q_n according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of V(TQ_n)∩E(TQ_n), we prove that TQ_n−F remains hamiltonian if |F|⩽n−2. Moreover, we prove that there exists a hamiltonian path in TQ_n−F joining any two vertices u, v in V(TQ_n)−F if |F|⩽n−3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQ_n is at most n−2 (n−3 respectively).     

Long paths in hypercubes with conditional node-faults

Let F be a set of f?2n-5 faulty nodes in an n-cube Q_n such that every node of Q_n still has at least two fault-free neighbors. Then we show that Q_n-F contains a path of length at least 2ⁿ-2f-1 (respectively, 2ⁿ-2f-2) between any two nodes of odd (respectively, even) distance. Since the n-cube is bipartite, the path of length 2ⁿ-2f-1 (or 2ⁿ-2f-2) turns out to be the longest if all faulty nodes belong to the same partite set. As a contribution, our study improves upon the previous result presented by [J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults, Information Sciences 176 (2006) 759-771] where only n-2 faulty nodes are considered.     

Fault-tolerant edge-pancyclicity of locally twisted cubes

The n-dimensional locally twisted cube LTQ_n is a new variant of the hypercube, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of LTQ_n, and shows that if LTQ_n (n ? 3) contains at most n − 3 faulty vertices and/or edges then, for any fault-free edge e and any integer ? with 6 ? ? ? 2ⁿ − f_v, there is a fault-free cycle of length ? containing the edge e, where f_v is the number of faulty vertices. The result is optimal in some senses. The proof is based on the recursive structure of LTQ_n.     

Path bipancyclicity of hypercubes

A bipartite graph is vertex-bipancyclic (respectively, edge-bipancyclic) if every vertex (respectively, edge) lies in a cycle of every even length from 4 to |V(G)| inclusive. It is easy to see that every connected edge-bipancyclic graph is vertex-bipancyclic. An n-dimensional hypercube, or n-cube denoted by Qn, is well known as bipartite and one of the most efficient networks for parallel computation. In this paper, we study a stronger bipancyclicity of hypercubes. We prove that every n-dimensional hypercube is (2n−4)-path-bipancyclic for n?3. That is, for any path P of length k with 1?k?2n−4 and any integer l with max{2,k}?l?²n−1, an even cycle C of length 2l can be found in Qn such that the path P is included in C for n?3.     

Edge-fault-tolerant edge-bipancyclicity of hypercubes

In this paper, we consider the problem embedding a cycle into the hypercube Qn with existence of faulty edges and show that for any edge subset F of Qn with |F|?n−1 every edge of Qn−F lies on a cycle of every even length from 6 to n² inclusive provided n?4 and all edges in F are not incident with the same vertex. This result improves some known results.     

Many-to-many disjoint paths in faulty hypercubes

This paper considers the problem of many-to-many disjoint paths in the hypercube Q_n with f_v faulty vertices and f_e faulty edges, and obtains the following result. For any integer k with 1?k?n-1, any two sets S and T of k fault-free vertices in different parts, if f_v+f_e?n-k-1, then there exist k disjoint fault-free (S,T)-paths in Q_n which contains at least 2ⁿ-2f_v vertices. This result is optimal in the worst case.     

Embedding paths of variable lengths into hypercubes with conditional link-faults

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path embedding of variable lengths in the range from the shortest to the longest. Let F be a set consisting of faulty links in a wounded n-cube Q_n, in which every node is still incident to at least two fault-free links. Then we show that Q_n-F has a path of any odd (resp. even) length in the range from the distance to 2ⁿ-1 (resp. 2ⁿ-2) between two arbitrary nodes even if |F|=2n-5. In order to tackle this problem, we also investigate the fault diameter of an n-cube with hybrid node and link faults.     

Path embeddings in faulty 3-ary n-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for distributed-memory parallel systems. In this paper, we study the problem of embedding paths of various lengths into faulty 3-ary n-cubes and prove that a faulty 3-ary n-cube with f?2n-3 faulty vertices admits a path of every length from 2n-1 to 3ⁿ-f-1 connecting any two distinct healthy vertices. This result is optimal with respect to the number of vertex faults tolerated.     

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Q_n is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Q_n−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Q_n) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Q_n when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y.     

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.     

An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges

In this paper, we study fault-tolerant routing in bijective connection networks with restricted faulty edges. First, we prove that the probability that all the incident edges of an arbitrary node become faulty in an n-dimensional bijective connection network, denoted by X_n, is extremely low when n becomes sufficient large. Then, we give an O(n) algorithm to find a fault-free path of length at most n+3⌈log₂∣F∣⌉+1 between any two different nodes in X_n if each node of X_n has at least one fault-free incident edge and the number of faulty edges is not more than 2n−3. In fact, we also for the first time provide an upper bound of the fault diameter of all the bijective connection networks with the restricted faulty edges. Since the family of BC networks contains hypercubes, crossed cubes, Möbius cubes, etc., all the results are appropriate for these cubes.     

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.     

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

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

Conditional fault diagnosis of hierarchical hypercubes

The design of large dependable multiprocessor systems requires quick and precise mechanisms for detecting the faulty nodes. The system-level fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the hierarchical hypercube HHC _n when the number of faulty vertices is up to two or three times of the traditional connectivity. Based on this fault resiliency, we establish that the conditional diagnosability of HHC _n (n=2 ^m +m, m≥2) under the comparison model is 3m?2, which is about three times of the traditional diagnosability.     

Long paths in hypercubes with a quadratic number of faults

A path between distinct vertices u and v of the n-dimensional hypercube Q_n avoiding a given set of f faulty vertices is called long if its length is at least 2ⁿ-2f-2. We present a function (n)=Θ(n²) such that if f(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q_n. Moreover, the bound provided by (n) is asymptotically optimal. Furthermore, we show that assuming f(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.