Abstract
The convex excess ce(G) of a graph G is introduced as inline image where the summation goes over all convex cycles of G. It is proved that for a partial cube G with n vertices, m edges, and isometric dimension i(G), inequality 2n−m−i(G)−ce(G)≤2 holds. Moreover, the equality holds if and only if the so-called zone graphs of G are trees. This answers the question from Bre inline image r et al. [Tiled partial cubes, J Graph Theory 40 (2002) 91–103] whether partial cubes admit this kind of inequalities. It is also shown that a suggested inequality from Bre inline image r et al. [Tiled partial cubes, J Graph Theory 40 (2002) 91–103] does not hold. Copyright © 2011 John Wiley & Sons, Ltd.
Original language | English |
---|---|
Pages (from-to) | 356-369 |
Number of pages | 14 |
Journal | Journal of Graph Theory |
Volume | 69 |
Issue number | 4 |
Early online date | 3 Mar 2011 |
DOIs | |
Publication status | Published - 1 Apr 2012 |