In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.
History Firsov (1965) was the first to study isometric embeddings of graphs into hypercubes. The graphs that admit such embeddings were characterized by Djoković (1973) and Winkler (1984), and were later named partial cubes. A separate line of research on the same structures, in the terminology of families of sets rather than of hypercube labelings of graphs, was followed by Kuzmin & Ovchinnikov (1975) and Falmagne & Doignon (1997), among others.
Examples
Every tree is a partial cube. For, suppose that a tree T has m edges, and number these edges (arbitrarily) from 0 to m – 1. Choose a root vertex r for the tree, arbitrarily, and label each vertex v with a string of m bits that has a 1 in position i whenever edge i lies on the path from r to v in T. For instance, r itself will have a label that is all zero bits, its neighbors will have labels with a single 1-bit, etc. Then the Hamming distance between any two labels is the distance between the two vertices in the tree, so this labeling shows that T is a partial cube. Every hypercube graph is itself a partial cube, which can be labeled with all the different bitstrings of length equal to the dimension of the hypercube. More complex examples include the following:
Consider the graph whose vertex labels consist of all possible (2n + 1)-digit bitstrings that have either n or n + 1 nonzero bits, where two vertices are adjacent whenever their labels differ by a single bit. This labeling defines an embedding of these graphs into a hypercube (the graph of all bitstrings of a given length, with the same adjacency-condition) that turns out to be distance-preserving. The resulting graph is a bipartite Kneser graph; the graph formed in this way with n = 2 has 20 vertices and 30 edges, and is called the Desargues graph. All median graphs are partial cubes. The trees and hypercube graphs are examples of median graphs. Since the median graphs include the squaregraphs, simplex graphs, and Fibonacci cubes, as well as the covering graphs of finite distributive lattices, these are all partial cubes. The planar dual graph of an arrangement of lines in the Euclidean plane is a partial cube. More generally, for any hyperplane arrangement in Euclidean space of any number of dimensions, the graph that has a vertex for each cell of the arrangement and an edge for each two adjacent cells is a partial cube. A partial cube in which every vertex has exactly three neighbors is known as a cubic partial cube. Although several infinite families of cubic partial cubes are known, together with many other sporadic examples, the only known cubic partial cube that is not a planar graph is the Desargues graph. The underlying graph of any antimatroid, having a vertex for each set in the antimatroid and an edge for every two sets that differ by a single element, is always a partial cube. The Cartesian product of any finite set of partial cubes is another partial cube. A subdivision of a complete graph is a partial cube if and only if either every complete graph edge is subdivided into a two-edge path, or there is one complete graph vertex whose incident edges are all unsubdivided and all non-incident edges have been subdivided into even-length paths.
The Djoković–Winkler relation Many of the theorems about partial cubes are based directly or indirectly upon a certain binary relation defined on the edges of the graph. This relation, first described by Djoković (1973) and given an equivalent definition in terms of distances by Winkler (1984), is denoted by Θ {\displaystyle \Theta } . Two edges e = { x , y } {\displaystyle e=\{x,y\}} and f = { u , v } {\displaystyle f=\{u,v\}} are defined to be in the relation Θ {\displaystyle \Theta } , written e Θ f {\displaystyle e{\mathrel {\Theta }}f} , if
d ( x , u ) + d ( y , v ) ≠ d ( x , v ) + d ( y , u ) {\displaystyle d(x,u)+d(y,v)\not =d(x,v)+d(y,u)} . This relation is reflexive and symmetric, but in general it is not transitive. Winkler showed that a connected graph is a partial cube if and only if it is bipartite and the relation Θ {\displaystyle \Theta } is transitive. In this case, it forms an equivalence relation and each equivalence class separates two connected subgraphs of the graph from each other. A Hamming labeling may be obtained by assigning one bit of each label to each of the equivalence classes of the Djoković–Winkler relation; in one of the two connected subgraphs separated by an equivalence class of edges, all of the vertices have a 0 in that position of their labels, and in the other connected subgraph all of the vertices have a 1 in the same position.
… excerpt ends here. Continue reading the full article.
