On cube-free median graphs

Let G   be a cube-free median graph. It is proved that k/2⩾n-1⩾m/2n⩾s⩾r-1, where n, m, s, k, and r   are the number of vertices, edges, squares, ΘΘ-classes, and the number of edges in a smallest ΘΘ-class of G, respectively. Moreover, the equalities characterize Cartesian products of two trees of the same order. The cube polynomial of cube-free median graphs is also considered and it is shown that planar cube-free median graphs can be recognized in linear time.