Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649059 | Discrete Mathematics | 2007 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Boštjan Brešar, Sandi Klavžar, Riste Škrekovski,