Locally Twisted Cube Graph

The -dimensional locally twisted cube graph , for , is a graph constructed recursively from the square graph by joining two copies of the preceding graph with a specified perfect matching (Yang et al. 2005). It is a variant of the hypercube graph with the same vertex count, edge count, and vertex degree, but a smaller graph diameter for .

Label the vertices by binary strings of length . Start with , labeled so that two vertices are adjacent when their labels differ in a single bit. For , prefix the labels of two disjoint copies of with 0 and 1, respectively. Retain all edges within the copies and add edges of the form

(1)

where denotes XOR, or addition modulo 2. Thus the last bit determines whether the second bit changes along an edge joining the copies. Equivalently, number the bit positions from left to right. The neighbors of a label are obtained by flipping either of its last two bits separately, or by flipping bit and adding the last bit modulo 2 to bit , for (Hu et al. 2007, p. 4). In particular, labels of adjacent vertices differ in at most two consecutive positions. The specified perfect matching distinguishes this family from other twisting rules for hypercube graphs (Hu et al. 2007, pp. 1-4).

The construction gives a connected graph with vertices and edges. Each vertex has vertex degree , and the vertex connectivity is also (Yang et al. 2005). Its graph diameter is

(2)

where is the ceiling function (Yang et al. 2005, Ma and Xu 2006). This is roughly half the graph diameter of . The first members are identified in the following table up to graph isomorphism.

	locally twisted cube graph
2	square graph
3	Wagner graph

The graphs are triangle-free, but for they contain cycles of every length from 4 through (Yang et al. 2004). Consequently they are not bipartite for , in contrast to hypercube graphs. They are also Hamilton-connected for , so every two distinct vertices are endpoints of a Hamiltonian path (Yang et al. 2004, Ma and Xu 2006). Hu et al. (2007, p. 5) proved the stronger property that, for , every edge lies on a graph cycle of each length from 4 through .

General crossing-number bounds were obtained by Wang et al. (2011), with a published upper bound in Wang et al. (2017). The following table gives exact graph crossing numbers or upper bounds for .

	crossing number	reference
2	0	Wang et al. (2013)
3	1	Wang et al. (2013)
4	10	Wang et al. (2013)
5		Zhao et al. (2018, pp. 411, 417)
6		E. Weisstein (Nov. 2026)
7		Zhao et al. (2018, pp. 411, 417)
8		Zhao et al. (2018, pp. 411, 417)
9		Zhao et al. (2018, pp. 411, 417)
10		Zhao et al. (2018, pp. 411, 417)

For small , the -dimensional locally twisted cube graph will be implemented in a future version of the Wolfram Language as GraphData["LocallyTwistedCube", n].