The cube-connected cycle graph of order 
, sometimes denoted 
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).
Another construction gives 
as the node-to-circle
expansion of the hypercube graph 
(Leighton 1992, Brandenburg 2020) when vertices are labeled
as bitstrings and neighbors are determined by which coordinate flips, thus giving
replacement cycle positions that are exactly the coordinate indices.
The cube-connected cycle graph is bipartite for 
,
6, 8, ....
The case 
corresponds to the truncated cubical graph,
illustrated above in a number of embeddings.
The case 
is isomorphic to the 
truncated
square lattice graph, illustrated above, which is a subgraph of the torus
grid graph 
.
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, 84, 487, 2380, 12390, ... (E. Weisstein, Feb. 25, 2026).
