In graph theory, a partial cube is a graph that is an isometric subgraph of a hypercube.[1] 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.[2]

Examples

An example of a partial cube with a Hamming labeling on its vertices. This graph is also a median graph.

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:

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 . Two edges and are defined to be in the relation , written , if . 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  is transitive.[8] 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.

Recognition

Partial cubes can be recognized, and a Hamming labeling constructed, in  time, where  is the number of vertices in the graph.[9] Given a partial cube, it is straightforward to construct the equivalence classes of the Djoković–Winkler relation by doing a breadth first search from each vertex, in total time ; the -time recognition algorithm speeds this up by using bit-level parallelism to perform multiple breadth first searches in a single pass through the graph, and then applies a separate algorithm to verify that the result of this computation is a valid partial cube labeling.

Dimension

The isometric dimension of a partial cube is the minimum dimension of a hypercube onto which it may be isometrically embedded, and is equal to the number of equivalence classes of the Djoković–Winkler relation. For instance, the isometric dimension of an -vertex tree is its number of edges, . An embedding of a partial cube onto a hypercube of this dimension is unique, up to symmetries of the hypercube.[10]

Every hypercube and therefore every partial cube can be embedded isometrically into an integer lattice. The lattice dimension of a graph is the minimum dimension of an integer lattice into which the graph can be isometrically embedded. The lattice dimension may be significantly smaller than the isometric dimension; for instance, for a tree it is half the number of leaves in the tree (rounded up to the nearest integer). The lattice dimension of any graph, and a lattice embedding of minimum dimension, may be found in polynomial time by an algorithm based on maximum matching in an auxiliary graph.[11]

Other types of dimension of partial cubes have also been defined, based on embeddings into more specialized structures.[12]

Application to chemical graph theory

Isometric embeddings of graphs into hypercubes have an important application in chemical graph theory. A benzenoid graph is a graph consisting of all vertices and edges lying on and in the interior of a cycle in a hexagonal lattice. Such graphs are the molecular graphs of the benzenoid hydrocarbons, a large class of organic molecules. Every such graph is a partial cube. A Hamming labeling of such a graph can be used to compute the Wiener index of the corresponding molecule, which can then be used to predict certain of its chemical properties.[13]

A different molecular structure formed from carbon, the diamond cubic, also forms partial cube graphs.[14]

Notes

  1. ^ Ovchinnikov (2011), Definition 5.1, p. 127.
  2. ^ Ovchinnikov (2011), p. 174.
  3. ^ Ovchinnikov (2011), Section 5.11, "Median Graphs", pp. 163–165.
  4. ^ Ovchinnikov (2011), Chapter 7, "Hyperplane Arrangements", pp. 207–235.
  5. ^ Eppstein (2006).
  6. ^ Ovchinnikov (2011), Section 5.7, "Cartesian Products of Partial Cubes", pp. 144–145.
  7. ^ Beaudou, Gravier & Meslem (2008).
  8. ^ Winkler (1984), Theorem 4. See also Ovchinnikov (2011), Definition 2.13, p.29, and Theorem 5.19, p. 136.
  9. ^ Eppstein (2008).
  10. ^ Ovchinnikov (2011), Section 5.6, "Isometric Dimension", pp. 142–144, and Section 5.10, "Uniqueness of Isometric Embeddings", pp. 157–162.
  11. ^ Hadlock & Hoffman (1978); Eppstein (2005); Ovchinnikov (2011), Chapter 6, "Lattice Embeddings", pp. 183–205.
  12. ^ Eppstein (2009); Cabello, Eppstein & Klavžar (2011).
  13. ^ Klavžar, Gutman & Mohar (1995), Propositions 2.1 and 3.1; Imrich & Klavžar (2000), p. 60; Ovchinnikov (2011), Section 5.12, "Average Length and the Wiener Index", pp. 165–168.
  14. ^ Eppstein (2009).

References