## 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

PDF