The cube-connected cycle graph of order is the graph obtained by replacing each vertex in a -dimensional hypercube by a cycle of length . They were introduced by Preparata and Vuillemin (1981) and share many properties with hypercubes, but have the additional desirable property that for , every vertex has degree three. The cube-connected cycles contain self-loops for and 2, but are simple for .
The th order cube-connected cycle can be constructed on the set of nodes indexed by pairs of numbers , with and , where each node is connected to the three other nodes , ), and , where denotes the bitwise XOR operation on and considered as binary numbers.
The th order cube-connected cycle can also be constructed as the Cayley graph of the group acting on binary words of length generated by the group elements that rotate the bits of a word one position left, rotate the bits of a word one position right, and invert the first bit of a word (Akers and Krishnamurthy 1989; Annexstein et al. 1990).
The case is a subgraph of the torus grid graph .
The special case corresponds to the truncated cubical graph, illustrated above in a number of embeddings.
The -cube-connected cycle graph can be generated in the Wolfram Language using FromEntity[Entity["Graph", "CubeConnectedCycle", n]], and precomputed properties of small cube-connected cycle graphs are available in the Wolfram Language using GraphData["CubeConnectedCycle", n].
For , the graph diameter of a cube-connected cycle graph is .
Sýkora and Vrt'o (1993) established bounds on the graph crossing number of the -cube connected cycle graph as
(Clancy et al. 2019). However, these bounds are quite loose compared to upper bounds computable using QuickCross (Haythorpe) which, for , 4, 5, ... and moderate run time, can be obtained as 0, 16, 88, 521, 2623, ... (E. Weisstein, Apr. 29, 2019).