Cube-connected cycles

The cube-connected cycles of order 3, arranged geometrically on the vertices of a truncated cube.

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.

Definition

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

Properties

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.[1] 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 (2n  x  1, (y + n/2) mod n).[2] Sýkora & Vrťo (1993) showed that the crossing number of CCCn is ((1/20) + o(1)) 4n.

According to the Lovász conjecture, the cube-connected cycle graph should always contain a Hamiltonian cycle, and this is now known to be true. More generally, although these graphs are not pancyclic, they contain cycles of all but a bounded number of possible even lengths, and when n is odd they also contain many of the possible odd lengths of cycles.[3]

Parallel processing application

Cube-connected cycles were investigated by Preparata & Vuillemin (1981), who applied these graphs as the interconnection pattern of a network connecting the processors in a parallel computer. In this application, cube-connected cycles have the connectivity advantages of hypercubes while only requiring three connections per processor. Preparata and Vuillemin showed that a planar layout based on this network has optimal area × time2 complexity for many parallel processing tasks.

Notes

References

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.