A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes H n . The n ‐dimensional twisted hypercube H n is obtained from two copies of the ( n − 1 ) ‐dimensional twisted hypercube H n − 1by adding a perfect matching between the vertices of these two copies of H n − 1 . We prove that the n ‐dimensional twisted hypercube H n has diameter( 1 + o ( 1 ) ) n / log 2 n . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order o ( n / log 2 n ) . Another type of hypercube variant Z n , kthat has similar structure and properties as H n is also discussed in the last section.