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

, a folded cube graph is an

undirected graph 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 ...

formed from 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 adding to it a

perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...

that connects ''opposite'' pairs of hypercube vertices.

Construction

The folded cube graph of dimension ''k'' (containing 2^{''k'' − 1} vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of dimension ''k'' − 1. (In a hypercube with 2^''n'' vertices, a pair of vertices are ''opposite'' if the shortest path between them has length ''n''.) It can, equivalently, be formed from a hypercube graph (also) of dimension ''k'', which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices.

Properties

A dimension-''k'' folded cube graph is a ''k''- regular with 2^{''k'' − 1} vertices and 2^{''k'' − 2}''k'' edges. The

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the dimension-''k'' folded cube graph is two when ''k'' is even (that is, in this case, the graph is bipartite) and four when ''k'' is odd. The

odd girth In graph theory, the girth of an undirected graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (that is, it is a forest), its girth is defined to be infinity. For example, a 4-cycle (square) h ...

of a folded cube of odd dimension is ''k'', so for odd ''k'' greater than three the folded cube graphs provide a class of

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

s with chromatic number four and arbitrarily large odd girth. As a

distance-regular graph In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . ...

with odd girth ''k'' and diameter (''k'' − 1)/2, the folded cubes of odd dimension are examples of generalized odd graphs. When ''k'' is odd, the

bipartite double cover In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, canon ...

of the dimension-''k'' folded cube is the dimension-''k'' cube from which it was formed. However, when ''k'' is even, the dimension-''k'' cube is a double cover but not the ''bipartite'' double cover. In this case, the folded cube is itself already bipartite. Folded cube graphs inherit from their hypercube subgraphs the property of having 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 from the hypercubes that double cover them the property of being a

distance-transitive graph In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carrie ...

. When ''k'' is odd, the dimension-''k'' folded cube contains as a subgraph a

complete binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...

with 2^''k'' − 1 nodes. However, when ''k'' is even, this is not possible, because in this case the folded cube is a bipartite graph with equal numbers of vertices on each side of the bipartition, very different from the nearly two-to-one ratio for the bipartition of a complete binary tree.

Examples

*The folded cube graph of dimension three is a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

''K''₄. *The folded cube graph of dimension four is the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

''K''_4,4. *The folded cube graph of dimension five is the

Clebsch graph In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it wa ...

. *The folded cube graph of dimension six is the

Kummer graph Kummer is a German surname. Notable people with the surname include: * Bernhard Kummer (1897–1962), German Germanist *Clare Kummer (1873—1958), American composer, lyricist and playwright *Clarence Kummer (1899–1930), American jockey * Christ ...

, i.e. the Levi graph of the Kummer point-plane configuration.

Applications

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

, folded cube graphs have been studied as a potential

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

, as an alternative to the hypercube. Compared to a ''hypercube'', a ''folded cube'' with the same number of nodes has nearly the same vertex degree but only half 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 ...

. Efficient

distributed algorithm A distributed algorithm is an algorithm designed to run on computer hardware constructed from interconnected processors. Distributed algorithms are used in different application areas of distributed computing, such as telecommunications, scientific ...

s (relative to those for a ''hypercube'') are known for broadcasting information in a folded cube.; .

Notes

References

*. *. *. *. *. *.

External links

*{{mathworld, title=Folded Cube Graph, urlname=FoldedCubeGraph, mode=cs2 Parametric families of graphs Regular graphs