The cube-connected cycle graph of order 
, sometimes denoted 
, is the graph obtained by replacing
each vertex in an 
-dimensional hypercube graph
by a cycle of length 
. They were introduced by Preparata and Vuillemin (1981) and
share many properties with hypercube graphs, 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 drawings.
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. 2020). 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, 81, 480, 2297, 10374, ... (E. Weisstein, Feb. 25-Oct. 1, 2026),
the first two of which are exact.
