Median Graph - Additional Properties

Additional Properties

• The Cartesian product of every two median graphs is another median graph. Medians in the product graph may be computed by independently finding the medians in the two factors, just as medians in grid graphs may be computed by independently finding the median in each linear dimension.

• The windex of a graph measures the amount of lookahead needed to optimally solve a problem in which one is given a sequence of graph vertices s_i, and must find as output another sequence of vertices t_i minimizing the sum of the distances d(s_i,t_i) and d(t_{i − 1},t_i). Median graphs are exactly the graphs that have windex 2. In a median graph, the optimal choice is to set t_i = m(t_{i − 1},s_i,s_{i + 1}).

• The property of having a unique median is also called the unique Steiner point property. An optimal Steiner tree for three vertices a, b, and c in a median graph may be found as the union of three shortest paths, from a, b, and c to m(a,b,c). Bandelt & Barthélémy (1984) study more generally the problem of finding the vertex minimizing the sum of distances to each of a given set of vertices, and show that it has a unique solution for any odd number of vertices in a median graph. They also show that this median of a set S of vertices in a median graph satisfies the Condorcet criterion for the winner of an election: compared to any other vertex, it is closer to a majority of the vertices in S.

• As with partial cubes more generally, every median graph with n vertices has at most (n/2) log₂ n edges. However, the number of edges cannot be too small: Klavžar, Mulder & Škrekovski (1998) prove that in every median graph the inequality 2n − m − k ≤ 2 holds, where m is the number of edges and k is the dimension of the hypercube that the graph is a retract of. This inequality is an equality if and only if the median graph contains no cubes. This is a consequence of another identity for median graphs: the Euler characteristic Σ (-1)dim(Q) is always equal to one, where the sum is taken over all hypercube subgraphs Q of the given median graph.

• The only regular median graphs are the hypercubes.