On the spanning connectivity and spanning laceability of hypercube-like networks

Let u and v be any two distinct nodes of an undirected graph G, which is k-connected. For 1≤w≤k, a w-container C(u,v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u,v) of G is a w∗-container if it contains all the nodes of G. A graph G is w∗-connected if there exists a w∗-container between any two distinct nodes. A bipartite graph G is w∗-laceable if there exists a w∗-container between any two nodes from different parts of G. Let G0=(V0,E0) and G1=(V1,E1) be two disjoint graphs with |V0|=|V1|. Let E={(v,ϕ(v))∣v∈V0,ϕ(v)∈V1, and ϕ:V0→V1 is a bijection}. Let G=G0⊕G1=(V0∪V1,E0∪E1∪E). The set of n-dimensional hypercube-like graph is defined recursively as (a) , K2= complete graph with two nodes, and (b) if G0 and G1 are in , then G=G0⊕G1 is in . Let and G is bipartite} and . In this paper, we show that every graph in is w∗-laceable for every w, 1≤w≤n. It is shown that a constructed -graph H can not be 4∗-connected. In addition, we show that every graph in is w∗-connected for every w, 1≤w≤3.