Super Spanning Connectivity of the Folded Divide-and-SwapCube

Abstract

A k*-container of a graph G is a set of k disjoint paths between any pair of nodes whose union covers all nodes of G. The spanning connectivity of G, κ*(G), is the largest k, such that there exists a j*-container between any pair of nodes of G for all 1≤j≤k. If κ*(G)=κ(G), then G is super spanning connected. Spanning connectivity is an important property to measure the fault tolerance of an interconnection network. The divide-and-swap cube DSCn is a newly proposed hypercube variant, which reduces the network cost from O(n2) to O(nlog2n) compared with the hypercube and other hypercube variants. The folded divide-and-swap cube FDSCn is proposed based on DSCn to reduce the diameter of DSCn. Both DSCn and FDSCn possess many better properties than hypercubes. In this paper, we investigate the super spanning connectivity of FDSCn where n=2d and d≥1. We show that κ*(FDSCn)=κ(FDSCn)=d+2, which means there exists an m-DPC(node-disjoint path cover) between any pair of nodes in FDSCn for all 1≤m≤d+2.

Keywords

• folded divide-and-swap cube
• node-disjoint path cover
• interconnection network
• Hamiltonian
• super spanning connectivity