Cube-connected cycles

In graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by Preparata & Vuillemin (1981) for use as a network topology in parallel computing.

The cube-connected cycles of order n (denoted CCC_n) can be defined as a graph formed from a set of n2ⁿ nodes, indexed by pairs of numbers (x, y) where 0 ≤ x < 2ⁿ and 0 ≤ y < n. Each such node is connected to three neighbors: (x, (y + 1) mod n), (x, (y − 1) mod n), and (x ⊕ 2^y, y), where "⊕" denotes the bitwise exclusive or operation on binary numbers.

The cube-connected cycles of order n is the Cayley graph of a group that acts on binary words of length n by rotation and flipping bits of the word. The generators used to form this Cayley graph from the group are the group elements that act by rotating the word one position left, rotating it one position right, or flipping its first bit. Because it is a Cayley graph, it is vertex-transitive: there is a symmetry of the graph mapping any vertex to any other vertex.

The diameter of the cube-connected cycles of order n is 2n + ⌊n/2⌋ − 2 for any n ≥ 4; the farthest point from (x, y) is (2ⁿ − x − 1, (y + n/2) mod n).Sýkora & Vrťo (1993) showed that the crossing number of CCC_n is ((1/20) + o(1)) 4ⁿ.

...
Wikipedia