A Hypercube Variant with Small Diameter
Xuding Zhu · Journal of Graph Theory · 2016
This article introduces a new variant of hypercubes . The n-dimensional twisted hypercube is obtained from two copies of the -dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n-dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.