Convex excess in partial cubes |
| |
Authors: | Sandi Klavžar Sergey Shpectorov |
| |
Affiliation: | 1. Faculty of Mathematics and Physics, University of Ljubljana, , Slovenia;2. Faculty of Natural Sciences and Mathematics, University of Maribor, , Slovenia;3. School of Mathematics, University of Birmingham Edgbaston, , United Kingdom |
| |
Abstract: | The convex excess ce(G) of a graph G is introduced as 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 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 r et al. [Tiled partial cubes, J Graph Theory 40 (2002) 91–103] does not hold. Copyright © 2011 John Wiley & Sons, Ltd. |
| |
Keywords: | partial cube hypercube convex excess zone graph |
|
|