graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the cube-connected cycles is an

undirected In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

cubic graph In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bip ...

, formed by replacing each vertex of a

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cubical graph, cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has ...

by a cycle. It was introduced by for use as a

network topology Network topology is the arrangement of the elements (Data link, links, Node (networking), nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, ...

parallel computing Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...

Definition

The cube-connected cycles of order ''n'' (denoted CCC_''n'') can be defined as a graph formed from a set of ''n''2^''n'' nodes, indexed by pairs of numbers (''x'', ''y'') where 0 ≤ ''x'' < 2^''n'' and 0 ≤ ''y'' < ''n''. Each such node is connected to three neighbors: , , and , where "⊕" denotes the

bitwise In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operat ...

exclusive or Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (on ...

operation on binary numbers. This graph can also be interpreted as the result of replacing each vertex of an ''n''-dimensional hypercube graph by an ''n''-vertex cycle. The hypercube graph vertices are indexed by the numbers ''x'', and the positions within each cycle by the numbers ''y''.

Properties

The cube-connected cycles of order ''n'' is the

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

of a

group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic iden ...

that

acts The Acts of the Apostles (, ''Práxeis Apostólōn''; ) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message to the Roman Empire. Acts and the Gospel of Luke make up a two-par ...

on binary words of length ''n'' by

rotation Rotation or rotational/rotary motion is the circular movement of an object around a central line, known as an ''axis of rotation''. A plane figure can rotate in either a clockwise or counterclockwise sense around a perpendicular axis intersect ...

and flipping bits of the word. 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 In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face i ...

: there is a symmetry of the graph mapping any vertex to any other vertex. The

diameter In geometry, a diameter of a circle is any straight line segment that passes through the centre of the circle and whose endpoints lie on the circle. It can also be defined as the longest Chord (geometry), chord of the circle. Both definitions a ...

of the cube-connected cycles of order ''n'' is for any n ≥ 4; the farthest point from (''x'', ''y'') is (2^''n'' − ''x'' − 1, (''y'' + ''n''/2) mod ''n''). showed that the crossing number of CCC_''n'' is ((1/20) + o(1)) 4^''n''. According to the Lovász conjecture, the cube-connected cycle graph should always contain a

Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...

, 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..

Parallel processing application

Cube-connected cycles were investigated by , who applied these graphs as the interconnection pattern of a

network Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...

connecting the processors in a

parallel computer Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different for ...

. 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 × time² complexity for many parallel processing tasks.

Notes

References

*. *. *. *. *. *{{citation , last1 = Sýkora , first1 = Ondrej , last2 = Vrťo , first2 = Imrich , title = On crossing numbers of hypercubes and cube connected cycles , journal = BIT Numerical Mathematics , volume = 33 , issue = 2 , year = 1993 , pages = 232–237 , doi = 10.1007/BF01989746, hdl = 11858/00-001M-0000-002D-92E4-9, s2cid = 15913153 , hdl-access = free. Network topology Parametric families of graphs Regular graphs