Folded cube graph
Encyclopedia
In graph theory
, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.
with 2k − 1 vertices and 2k − 2k edges.
The chromatic number of the order-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 of a folded cube of odd order is k, so for odd k greater than three the folded cube graphs provide a class of triangle-free graph
s with chromatic number four and arbitrarily large odd girth. As a distance-regular graph
with odd girth k and diameter (k − 1)/2, the folded cubes of odd order are examples of generalized odd graphs
.
When k is odd, the bipartite double cover
of the order-k folded cube is the order-k cube from which it was formed.
However when k is even, the order-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, and from the hypercubes that double cover them the property of being a distance-transitive graph
.
When k is odd, the order-k folded cube contains as a subgraph a complete binary tree with 2k − 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.
, folded cube graphs have been studied as a potential network topology
, 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
. Efficient distributed algorithms (relative to those for a hypercube) are known for broadcasting information in a folded cube.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects opposite pairs of hypercube vertices.
Construction
The folded cube graph of order k (containing 2k − 1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of order k − 1. (In a hypercube with 2n 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 order k, which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices.Properties
An order-k folded cube graph is k-regularRegular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
with 2k − 1 vertices and 2k − 2k edges.
The chromatic number of the order-k folded cube graph is two when k is even (that is, in this case, the graph is bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
) and four when k is odd. The odd girth of a folded cube of odd order is k, so for odd k greater than three the folded cube graphs provide a class of triangle-free graph
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
s with chromatic number four and arbitrarily large odd girth. As a distance-regular graph
Distance-regular graph
In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. Every distance-transitive graph is distance-regular...
with odd girth k and diameter (k − 1)/2, the folded cubes of odd order are examples of generalized odd graphs
Odd graph
In the mathematical field of graph theory, the odd graphs On are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.-Definition and examples:...
.
When k is odd, the bipartite double cover
Bipartite double cover
In graph theoretic mathematics, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs G × K2...
of the order-k folded cube is the order-k cube from which it was formed.
However when k is even, the order-k cube is a double cover
Covering graph
In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G...
but not the bipartite double cover. In this case, the folded cube is itself already bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
. Folded cube graphs inherit from their hypercube subgraphs the property of having a Hamiltonian cycle, and from the hypercubes that double cover them the property of being a distance-transitive graph
Distance-transitive graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y.A distance transitive...
.
When k is odd, the order-k folded cube contains as a subgraph a complete binary tree with 2k − 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 order three is a complete graphComplete graphIn 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.-Properties:...
K4. - The folded cube graph of order four is the complete bipartite graphComplete bipartite graphIn 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.- Definition :...
K4,4. - The folded cube graph of order five is the Clebsch graphClebsch graphIn the mathematical field of graph theory, the Clebsch graph is an undirected graph with 16 vertices and 40 edges. It is named after Alfred Clebsch, a German mathematician who discovered it in 1868...
. - The folded cube graph of order six is the Kummer graph.
Applications
In parallel computingParallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
, folded cube graphs have been studied as a potential network topology
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
, 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
Distance (graph theory)
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance...
. Efficient distributed algorithms (relative to those for a hypercube) are known for broadcasting information in a folded cube.