TOPICS
Search

Cube-Connected Cycle Graph


Cube-ConnectedCycle

The cube-connected cycle graph of order n is the graph obtained by replacing each vertex in a n-dimensional hypercube by a cycle of length n. They were introduced by Preparata and Vuillemin (1981) and share many properties with hypercubes, but have the additional desirable property that for n>1, every vertex has degree three. The cube-connected cycles contain self-loops for n=1 and 2, but are simple for n>=3.

The nth order cube-connected cycle can be constructed on the set of n·2^n nodes indexed by pairs of numbers (x,y), with 0<=x<=2^n-1 and 0<=y<=n-1, where each node (x,y) is connected to the three other nodes (x,(y+1) (mod n)), (x,(y-1) (mod n)), and (x direct sum 2^y,y), where A direct sum B denotes the bitwise XOR operation on A and B considered as binary numbers.

The nth order cube-connected cycle can also be constructed as the Cayley graph of the group acting on binary words of length n 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 n=4 is a subgraph of the torus grid graph C_8 square C_8.

TruncatedCubicalGraph

The special case n=3 corresponds to the truncated cubical graph, illustrated above in a number of embeddings.

The n-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 n>3, the graph diameter of a cube-connected cycle graph is 2n+|_n/2_|-2.

Sýkora and Vrt'o (1993) established bounds on the graph crossing number of the n-cube connected cycle graph as

 (4^n)/(20)-3(n+1)2^(n-2)<cr(CCC_n)<(4^n)/6+3n^22^(n-3)

(Clancy et al. 2019). However, these bounds are quite loose compared to upper bounds computable using QuickCross (Haythorpe) which, for n=3, 4, 5, ... and moderate run time, can be obtained as 0, 16, 88, 521, 2623, ... (E. Weisstein, Apr. 29, 2019).


See also

Hypercube Graph, Truncated Cubical Graph

Explore with Wolfram|Alpha

References

Akers, S. B. and Krishnamurthy, B. "A Group-Theoretic Model for Symmetric Interconnection Networks." IEEE Trans. Computers 38, 555-566, 1989.Annexstein, F.; Baumslag, M.; and Rosenberg, A. L. "Group Action Graphs and Parallel Architectures." SIAM J. Computing 19, 544-569, 1990.Clancy, K.; Haythorpe, M.; and Newcombe, A. "A Survey of Graphs with Known or Bounded Crossing Numbers." 15 Feb 2019. https://arxiv.org/pdf/1901.05155.pdf.Friš, I.; Havel, I.; and Liebl, P. "The Diameter of the Cube-Connected Cycles." Inform. Proc. Lett. 61, 157-160, 1997.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 641-642, 2006.Haythorpe, M. "QuickCross--Crossing Number Problem." http://www.flinders.edu.au/science_engineering/csem/research/programs/flinders-hamiltonian-cycle-project/quickcross.cfm.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, 2003.Preparata, F. P. and Vuillemin, J. "The Cube-Connected Cycles: A Versatile Network for Parallel Computation." Comm. ACM 24, 300-309, 1981.Sýkora, O. and Vrt'o, I. "On Crossing Numbers of Hypercubes and Cube Connected Cycles." BIT Num. Math. 33, 232-237, 1993.

Cite this as:

Weisstein, Eric W. "Cube-Connected Cycle Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Cube-ConnectedCycleGraph.html

Subject classifications