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, with each self-loop
counted twice. The cube-connected cycles contain self-loops
for
and multiple edges for
, 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 for
, each node
is connected to the three other nodes
,
, and
, where
denotes the bitwise XOR
operation on
and
considered as binary numbers. For
and 2, the replacement cycles
retain their self-loops and multiple
edges, respectively.
For , 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 , 4, 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, ..., give 0, 16, 80, 469, 2288, 10107, ...,
the first two of which are exact. The searches for
were continued until each search stream for each
of the three embedding schemes had run for one week without improving its own best
crossing count (E. Weisstein, Nov. 1, 2026).