graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the cube-connected cycles is an

undirected In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

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

, formed by replacing each

vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...

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 cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

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

network topology Network topology is the arrangement of the elements ( links, nodes, etc.) of a communication network. Network topology can be used to define or describe the arrangement of various types of telecommunication networks, including command and contro ...

parallel computing 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 fo ...

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

exclusive or Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...

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 that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayle ...

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

that

acts The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...

on binary words of length ''n'' by

rotation Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...

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

: 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 center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

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 mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

, 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, hdl-access = free. Network topology Parametric families of graphs Regular graphs