Fault tolerance of hypercube like networks: Spanning laceability under edge faults

Abstract Given two vertices u and v in a connected undirected graph G, a w⁎-container C ( u , v ) is a set of w internally vertex disjoint paths between u and v spanning all the vertices in G. A bipartite graph G is w ⁎ -laceable if there exists a w ⁎ -container between any two vertices belonging to different partitions of G. In [8] , [33] a class B n ′ of bipartite graphs called hypercube-like bipartite netwroks was defined. In [22] , Lin et al. showed that every graph in B n ′ is w ⁎ -laceable for every 1 ≤ w ≤ n . We define a graph is f-edge fault tolerant w ⁎ -laceable if G − F is w ⁎ -lacaable for any arbitrary subset F of edges of G with | F | ≤ f . In this paper we show that every graph in B n ′ is f-edge-fault tolerant w ⁎ -laceable for every 0 ≤ f ≤ n − 2 and 1 ≤ w ≤ n − f which generalize Lin's result. We also give generalization of two other results in [22] , [27] .