Median Graph - Equivalent Definitions

Equivalent Definitions

In an arbitrary graph, for each two vertices a and b, define the interval of vertices that lie on shortest paths

I(a,b) = {v | d(a,b) = d(a,v) + d(v,b)}.

A median graph is defined by the property that, for every three vertices a, b, and c, these intervals intersect in a single point:

For all a, b, and c, |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.

Equivalently, for every three vertices a, b, and c one can find a vertex m(a,b,c) such that the unweighted distances in the graph satisfy the equalities

• d(a,b) = d(a,m(a,b,c)) + d(m(a,b,c),b)
• d(a,c) = d(a,m(a,b,c)) + d(m(a,b,c),c)
• d(b,c) = d(b,m(a,b,c)) + d(m(a,b,c),c)

and m(a,b,c) is the only vertex for which this is true.

It is also possible to define median graphs as the solution sets of 2-satisfiability problems, as the retracts of hypercubes, as the graphs of finite median algebras, as the Buneman graphs of Helly split systems, and as the graphs of windex 2; see the sections below.