The super laceability of the hypercubes

Abstract

A k-container C(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 less than or equal to k. A bipartite graph G with connectivity k is f-edge fault-tolerant super laceable if G - F is i*-laceable for any 1 less than or equal to i less than or equal to 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, Qr is f-edge fault-tolerant super laceable for any f less than or equal to r - 2. (C) 2004 Elsevier B.V. All rights reserved.