Convex excess and Euler-type inequality for partial cubes
Sandi Klavÿzar, Sergey V. Shpectorov · 2008
The convex excess e(G) of a graph G is introduced as P (|C|−4)/2 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), 2n−m−i(G)−e(G) ≤ 2. Moreover, the equality holds if and only if the so-called zone graphs of G are trees. This answers the question from [2] whether partial cubes admit an Eulertype inequality. It is also shown that a suggestion for an Euler-type inequality from [2] does not hold.