For a partial cube (that is, an isometric subgraph of a hypercube)
G, quotient graphs G#,
Gτ, and G~
have the equivalence classes of the Djokovi\'c-Winkler relation as
the vertex set, while edges are defined in three different natural
ways. Several results on these quotients are proved and the
concepts are compared. For instance, for every graph G there
exists a median graph M such that G=Mτ. Triangle-free
and complete quotient graphs are treated and it is proved that for
a median graph G its τ-graph is triangle-free if and only
if G contains no convex K1,3. Connectedness and the
question of when quotients yield the same graphs are also treated.
|