Research On Properties Of Several Hypercubes Variants

The hypercube has been proved to be one of the most popular interconnection networks for its superior properties such as regularity, symmetry, strong hierarch, and strong fault tolerance and so on. But the hypercube is not an interconnection network whose all properties are optimal. So far, a number of hypercube variants such as the locally twisted cube and the twisted-cube have been proposed in the literature. In this paper, we first studied the embedding of meshes into n-dimensional twisted-cubes TN_n. Furthermore, owing to the shortcoming of LTQ_n and TN_nwith respect to upgrading, we proposed the super locally twisted cubes W_N and the super twisted-cubes S_N with N vertices, where n =「log2N」. The major research results are summarized in the following three aspects:(1) We studied the embedding of meshes into twisted-cubes. We found three major results in this section: For any integer n≥1, 2×2^n-1 mesh can be embedded into TN_n with dilation 1 and expansion 1; For any integer n≥4, an m×k(m≥3, k≥3) mesh cannot be embedded into TN_n with dilation 1; For any integer n≥4, two node-disjoint 4×2^n-3 meshes can be embedded into TN_n with dilation 2.(2) We proposed the super locally twisted cubes W_N . We obtained five major results as follows: The minimum degree of W_N satisfies n≤δ(W_N )≤n+ 1; The maximum degree of W_N satisfies n≤Δ(W_N )≤2 n+ 1; The vertex connectivity, edge connectivity and minimum vertex degree of W_N satisfiesκ(W_N) =λ(W_N) =δ(W_N); W_N is a Hamiltonian graph; The diameter of W_N satisfies「(n+3)/2」≤d(W_N)≤「(n+3)/2」+1(3) We proposed the super twisted-cubes S N. We obtained five major results as follows: The minimum degree ofS_Nsatisfies n≤δ( S_N )≤n+ 1; The maximum degree of S N satisfies n≤Δ( S_N)≤2n; The vertex connectivity, edge connectivity and minimum vertex degree ofS_N satisfiesκ(S_N)=λ(S_N)=δ(S_N);S_N is a Hamiltonian graph; The diameter of W_N satisfies d (S_N)≤「(n+1)/2」+1.