Bo\v stjan Bre\v sar, Sandi Klav\v zar
On partial cubes and graphs with convex intervals

Comment.Math.Univ.Carolinae 43,3 (2002) 537-545.

Abstract:A graph is called a partial cube if it admits an isometric embedding into a hypercube. Subdivisions of wheels are considered with respect to such embeddings and with respect to the convexity of their intervals. This allows us to answer in negative a question of Chepoi and Tardif from 1994 whether all bipartite graphs with convex intervals are partial cubes. On a positive side we prove that a graph which is bipartite, has convex intervals, and is not a partial cube, always contains a subdivision of $K_4$.

Keywords: isometric embeddings, hypercubes, partial cubes, convex intervals, subdivisions
AMS Subject Classification: 05C12, 05C75