Retracts of Hypercubes
A retraction of a graph G is an adjacency-preserving map from G to one of its subgraphs. More precisely, it is graph homomorphism φ from G to itself such that φ(v) = v for each vertex v in the subgraph φ(G). The image of the retraction is called a retract of G. Retractions are examples of metric maps: the distance between φ(v) and φ(w), for every v and w, is at most equal to the distance between v and w, and is equal whenever v and w both belong to φ(G). Therefore, a retract must be an isometric subgraph of G: distances in the retract equal those in G.
If G is a median graph, and a, b, and c are an arbitrary three vertices of a retract φ(G), then φ(m(a,b,c)) must be a median of a, b, and c, and so must equal m(a,b,c). Therefore, φ(G) contains medians of all triples of its vertices, and must also be a median graph. In other words, the family of median graphs is closed under the retraction operation.
A hypercube graph, in which the vertices correspond to all possible k-bit bitvectors and in which two vertices are adjacent when the corresponding bitvectors differ in only a single bit, is a special case of a k-dimensional grid graph and is therefore a median graph. The median of three bitvectors a, b, and c may be calculated by computing, in each bit position, the majority function of the bits of a, b, and c. Since median graphs are closed under retraction, and include the hypercubes, every retract of a hypercube is a median graph.
Conversely, every median graph must be the retract of a hypercube. This may be seen from the connection, described above, between median graphs and 2-satisfiability: let G be the graph of solutions to a 2-satisfiability instance; without loss of generality this instance can be formulated in such a way that no two variables are always equal or always unequal in every solution. Then the space of all truth assignments to the variables of this instance forms a hypercube. For each clause, formed as the disjunction of two variables or their complements, in the 2-satisfiability instance, one can form a retraction of the hypercube in which truth assignments violating this clause are mapped to truth assignments in which both variables satisfy the clause, without changing the other variables in the truth assignment. The composition of the retractions formed in this way for each of the clauses gives a retraction of the hypercube onto the solution space of the instance, and therefore gives a representation of G as the retract of a hypercube. In particular, median graphs are isometric subgraphs of hypercubes, and are therefore partial cubes. However, not all partial cubes are median graphs; for instance, a six-vertex cycle graph is a partial cube but is not a median graph.
As Imrich & Klavžar (2000) describe, an isometric embedding of a median graph into a hypercube may be constructed in time O(m log n), where n and m are the numbers of vertices and edges of the graph respectively.
Read more about this topic: Median Graph