Research On LHL-Cube Interconnection Networks And Their Properties

Parallel computing systems take important roles in computer science. As a key component of a parallel computing system, the properties of the interconnection network in it determine the performance of the whole system at a large scale. So far, many interconnection networks have been proposed. The hypercube has enjoyed popularity due to a lot of attractive properties, such as small diameter, high connectivity, symmetry etc. However, all properties of the hypercube are not the best because some variants of it have some better properties than it. Among these variants, the locally twisted cube has some superior properties over the hypercube with respect to diameter, Hamiltonian connectivity, etc. This paper proposes a kind of connection—the hyper-connection between the nodes of the hypercube and the nodes of the locally twisted cube. Thus, a new interconnection network called a LHL-cube is obtained by using this kind of connection. The following properties of the LHL-cube are studied in this paper: vertex connectivity, edge connectivity, Hamiltonian connectivity, diameter, embedding and the Hamiltonian connectivity with faulty edges, which show that the LHL-cube has some advantageous properties of the hypercuve and the locally twisted cube. The major research results are as follow:(1) The n dimensional LHL-cube is a regular graph with 2n vertexs and n×2^n-1edges. Its vertex connectivity is n and the edge connectivity is n ; it is Hamiltonian connected for n≥4; and the upper bound of its diameter is []n/2 +3.(2) For any integer n≥4,any cycle of length l (4≤l≤2 n)can be embedded into the n dimension LHL-cube with dilation 1; for any integer n≥1 and n≥2, 2×2^n-1 and 4×2^n-2meshes can be embedded into it with dilation 1 and expansion 1, respectively; for any integer n≥6,an 8×2^n-3mesh cannot be embedded into it with dilation 1 and expansion 1.(3) In the n dimension LHL-cube, if the number of fault edges is not larger than n-2, there must be a Hamiltonian path for n≥3; if the number of fault edges is not larger than n-3, there must be a Hamiltonian cycle path for n≥4.