mathworld.wolfram.com

Cube-Connected Cycle Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

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