Abstract A p‐value of a sequence π = (x1, x2,…, xk) of elements of a finite metric space (X, d) is an element x for which \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$\sum_{i=1}^{k}d^p(x,x_i)$\end{document} is minimum. The function ℓp with domain the set of all finite sequences defined by ℓp(π) = {x: x is a p‐value of π} is called the ℓp‐function on X. The ℓp‐functions with p = 1 and p = 2 are the well‐studied median and mean functions respectively. In this article, the ℓp‐function on finite trees is characterized axiomatically. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Partial cubes are defined as isometric subgraphs of hypercubes. For a partial cube G, its crossing graph G # is introduced as the graph whose vertices are the equivalence classes of the Djoković--Winkler relation $\Theta$, two vertices being adjacent if they cross on a common cycle. It is shown that every graph is the crossing graph of some median graph and that a partial cube G is 2-connected if and only if G # is connected. A partial cube G has a triangle-free crossing graph if and only if G is a cube-free median graph. This result is used to characterize the partial cubes having a tree or a forest as its crossing graph. An expansion theorem is given for the partial cubes with complete crossing graphs. Cartesian products are also considered. In particular, it is proved that G # is a complete bipartite graph if and only if G is the Cartesian product of two trees.

Let M(m,n) be the complexity of checking whether a graph G with medges and n vertices is a median graph. We show that the complexity of checking whether Gis triangle-free is at most O(M(m,m)). Conversely, we prove that the complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n,n)), where T(m,n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, there are as many median graphs as there are triangle-free graphs. Finally, these results enable us to prove that the complexity of recognizing planar median graphs is linear.