SUPEREXTENSIONS AND THE DEPTH OF MEDIAN GRAPHS

An invariant of convex structures-the depth-is used to study the structure of finite median graphs. The main result is a recursive description of graphs of given depth. This leads to a complete description of the cubical structure of the superextension λ(5) (answering a question in [19]) and to a (less complete) description of superextensions λ(r) for r > 5. An important tool is the construction of certain graphs ρ{variant}(r) of linked bipartitions of the r-point set r. For each r ≥ 3, the graphs λ(r) and ρ{variant}(r) have the same number of vertices, but they are isomorphic (modulo extreme points) for r ≤ 5 only. © 1991.