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.     

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-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.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

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.     

Edge-fault-tolerant bipanconnectivity of hypercubes

This paper shows that for any two distinct vertices u and v with distance d in the hypercube Q_n (n?3) with at most faulty edges and each vertex incident with least two fault-free edges, there exist fault-free uv-paths of length ? in Q_n for every ? with d+4???2ⁿ-1 and . This result improves some known results on edge-fault bipanconnectivity of hypercubes. The proof is based on the recursive structure of Q_n.     

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.     

Edge-bipancyclicity of star graphs with faulty elements

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S_n. Given a set F comprised of faulty vertices and/or edges in S_n with |F|≤n−3 and any fault-free edge e in S_n−F, we show that there exist cycles of every even length from 6 to n!−2|F_v| in S_n−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite S_n is n!−2|F_v| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|F_v|+2 to n!−2|F_v| can be embedded.     

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].     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

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 embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

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.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Fault-free cycles in folded hypercubes with more faulty elements

Let FFv (respectively, FFe) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional folded hypercube FQn. In this paper, we show that FQn−FFv−FFe contains a fault-free cycle with length at least n²−2|FFv| if |FFe|+|FFv|?2n−4 and |FFe|?n−1, where n?3. Our result improves the previously known result of [S.-Y. Hsieh, A note on cycle embedding in folded hypercubes with faulty elements, Information Processing Letters (2008), in press, doi:10.1016/j.ipl.2008.04.003] where |FFe|+|FFv|?n−1 and n?4.     

The super laceability of the hypercubes

A k-containerC(u,v) of a graph G is a set of k disjoint paths joining u to v. A k-container C(u,v) is a k∗-container if every vertex of G is incident with a path in C(u,v). A bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u, v from different partite set of G. A bipartite graph G with connectivity k is super laceable if it is i∗-laceable for all i?k. A bipartite graph G with connectivity k is f-edge fault-tolerant super laceable if G−F is i∗-laceable for any 1?i?k−f and for any edge subset F with |F|=f<k−1. In this paper, we prove that the hypercube graph Q_r is super laceable. Moreover, Q_r is f-edge fault-tolerant super laceable for any f?r−2.     

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.     

Linear array and ring embeddings in conditional faulty hypercubes

The n-dimensional hypercube Q_n is a graph having 2ⁿ vertices labeled from 0 to 2ⁿ−1. Two vertices are connected by an edge if their binary labels differ in exactly one bit position. In this paper, we consider the faulty hypercube Q_n with n⩾3 that each vertex of Q_n is incident to at least two nonfaulty edges. Based on this requirement, we prove that Q_n contains a hamiltonian path joining any two different colored vertices even if it has up to 2n−5 edge faults. Moreover, we show that there exists a path of length 2ⁿ−2 between any two the same colored vertices in this faulty Q_n. Furthermore, we also prove that the faulty Q_n still contains a cycle of every even length from 4 to 2ⁿ inclusive.     

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.     

Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

Let Wn denote any bipartite graph obtained by adding some edges to the n-dimensional hypercube Qn, and let S and T be any two sets of k vertices in different partite sets of Wn. In this paper, we show that the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn if and only if k=²n−1 or the graph Wn−(S∪T) has a perfect matching. Moreover, if the graph Wn−(S∪T) has a perfect matching M, then the graph Wn has k vertex-disjoint (S,T)-paths containing all vertices of Wn and all edges in M. And some corollaries are given.