The Z-cubes: a hypercube variant with small diameter

Abstract

This paper introduces a new variant of hypercubes, which we call Z-cubes. The n-dimensional Z-cube $H_n$ is obtained from two copies of the (n-1)-dimensional Z-cube $H_{n-1}$ by adding a special perfect matching between the vertices of these two copies of $H_{n-1}$. We prove that the n-dimensional Z-cubes $H_n$ has diameter $(1+o(1))n/{\log }_{2}n$. This greatly improves on the previous known variants of hypercube of dimension n, whose diameters are all larger than n/3. Moreover, any hypercube variant of dimension $n$ is an n-regular graph on $2^n$ vertices, and hence has diameter greater than $n/{\log }_{2}n$. So the Z-cubes are optimal with respect to diameters, up to an error of order $o(n/{\log }_{2}n)$. Another type of Z-cubes $Z_{n,k}$ which have similar structure and properties as $H_n$ are also discussed in the last section.

9 pages, 1 figure

Cited by in corpus (1)

• A note on minimum linear arrangement for BC graphs