Cube-Connected Cycle Graph -- from Wolfram MathWorld
- ️Weisstein, Eric W.
The cube-connected cycle graph of order is the graph obtained by replacing each vertex in a
-dimensional hypercube by a cycle
of length
.
They were introduced by Preparata and Vuillemin (1981) and share many properties
with hypercubes, but have the additional desirable property that for
, every vertex has degree three. The cube-connected cycles
contain self-loops for
and 2, but are simple for
.
The th
order cube-connected cycle can be constructed on the set of
nodes indexed by pairs of numbers
, with
and
, where each node
is connected to the three other nodes
,
), and
, where
denotes the bitwise XOR
operation on
and
considered as binary numbers.
The th
order cube-connected cycle can also be constructed as the Cayley
graph of the group acting on binary words of length
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
is a subgraph of the torus grid graph
.
The special case corresponds to the truncated
cubical graph, illustrated above in a number of embeddings.
The -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 ,
the graph diameter of a cube-connected cycle graph
is
.
Sýkora and Vrt'o (1993) established bounds on the graph crossing number of the -cube connected cycle graph as
(Clancy et al. 2019). However, these bounds are quite loose compared to upper bounds computable using QuickCross (Haythorpe) which, for , 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