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).
