Spanning Connectivity Of Hypercubes And The Laceability Of Transposition Networks

For a graph G and an integer k>0 and for u,v∈G with u≠v,a k-container C(u,v) of G is a set of k internally disjoint (u,v)-paths, and C(u,v) is called a k*-container if it contains all vertices of G. A graph G is k*-connected (or spanning k-connected) if for any u, v∈V(G) with u≠v, G has a k*-container between u and v. The spanning connectivity of a graph G, denoted k*(G), is the largest integer k such that G is i*-connected for 1≤i≤k if G is 1*-connected and undefined otherwise.A bipartite graph G is k*-laceable if for any u,v from different partite sets of G,there is a k*-container C(u,v). The hypercube Qn is i*-laceable for 1≤i≤ n, but it is not k*-connected since any bipartite graph G is not k*-connected for k≥3. What is the minimum number of independent edges that one can add to Qn so that the resulting graph has spanning connectivity at least k?In the first part of this paper, for 1< k<n, we define f(n,k)=min{|E’|:E’is independent and k*(Qn+E’)≥k} and prove that f(n,1)= f(n,2)= 2 and f(n, k)=2(k-2) for any 3≤k≤n. Moreover,we indicate the way how to add the 2(k-2) edges into Qn. In the second part of this paper, we study the laceability of transposition networks. An n-dimensional transposition network on n digits, denoted by TNn, is an undirected graph with a node set equivalent to Vn and an edge set En, where Vn is the set of n! distinct permutations of the set {1,2,...,n}, En={(p,Pi,j(p))| p ∈ Vn,1≤i<j≤n}, the transposition φij(p) is a function that interchanges the ith and jth digits of p. Then we prove that TNn is (Cn2)*-laceable.