Wednesday, January 9, 2008

Properties of Cube-connected Cycles

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 (Akers & Krishnamurthy 1989; Annexstein, Baumslag & Rosenberg 1990). 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.

The diameter of the cube-connected cycles of order n is \scriptstyle 2n\, +\, \lfloor n/2\rfloor \,-\, 2; the farthest point from (x, y) is (2nx − 1, (y + n/2) mod n) (Friš, Havel & Liebl 1997). Sýkora & Vrťo (1993) showed that the crossing number of CCCn is (1 + o(1))4n/20.

No comments: