On cube-free median graphs (Q864119)

For a median graph \(G\) with \(n\) vertices and \(m\) edges, let \(s\) denote the number of induced squares, \(k\) the number of Djoković-Winkler \(\Theta\)-classes, and \(r\) the minimum size of such a class. The authors first shortly reprove the known equalities for cube-free median graphs \(s=m-n+1\) and \(k=2n-m-2\). It is then shown that for such graphs one has \[ r-1 \leq \sqrt{s} \leq m/(2\sqrt{n})\leq \sqrt{n}-1 \leq k/2 \] with any equality if and only if \(G\) is the Cartesian square of a tree. Finally median graphs can be proven to be cube-free in linear time; it follows that planar cubic-free median graphs are recognisable in linear time.