A median degree from crossing graphs of median graphs

Abstract

The crossing graph $\mathrm{Cross}(M)$ of a median graph $M$ is defined as the graph whose vertices are the $\Theta$-classes of $M$ and whose edges connect two $\Theta$-classes whenever they cross. It is known that every graph $X$ can be realised as the crossing graph of some median graph. In this article, we initiate the study of the space ${\mathrm{Cross}}^{-1}(X)$ of all the median graphs with crossing graph $X$. First, we prove that two finite median graphs have isomorphic crossing graphs if and only if one can be obtained from the other by a sequence of elementary transformations we call slidings. Then, motivated by the fact that ${\mathrm{Cross}}^{-1}(X)$ always contains a single median graph of maximal degree, namely the simplex-graph of $X$, we introduce the median degree of $X$ as the smallest possible degree of a median graph in ${\mathrm{Cross}}^{-1}(X)$. We compute the median degree for some families of graphs and characterise the graphs with maximal median degree.

23 pages, 15 figures. Comments are welcome!