A new variation on hypercubes with smaller diameter (Q685501)

The paper presents a variation on the hypercube, denoted \(GQ_ n\) for Generalized Twisted Cube of dimension n, that contains many of the good properties of the hypercube with smaller diameter. For a given dimension \(n\), the new diameter is about \((2/3)n\). After discussing the basic properties of the \(GQ_ n\), an efficient routing algorithm is presented, and then \(GQ_ n\) is shown to be Hamiltonian. Also we show that the complete binary tree on \(2^ n-1\) nodes, which is not a subgraph of the \(n\)-dimensional hypercube, is a subgraph of the \(GQ_ n\).