Geodesic
On partial cubes and graphs with convex intervals
Commentationes Mathematicae Universitatis Carolinae, Tome 43 (2002) no. 3, pp. 537-545 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
Classification : 05C12, 05C75
Keywords: isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions 
@article{CMUC_2002_43_3_a14,
     author = {Bre\v{s}ar, Bo\v{s}tjan and Klav\v{z}ar, Sandi},
     title = {On partial cubes and graphs with convex intervals},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {537--545},
     year = {2002},
     volume = {43},
     number = {3},
     mrnumber = {1920530},
     zbl = {1090.05023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_2002_43_3_a14/}
}
TY  - JOUR
AU  - Brešar, Boštjan
AU  - Klavžar, Sandi
TI  - On partial cubes and graphs with convex intervals
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2002
SP  - 537
EP  - 545
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/CMUC_2002_43_3_a14/
LA  - en
ID  - CMUC_2002_43_3_a14
ER  - 
%0 Journal Article
%A Brešar, Boštjan
%A Klavžar, Sandi
%T On partial cubes and graphs with convex intervals
%J Commentationes Mathematicae Universitatis Carolinae
%D 2002
%P 537-545
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/CMUC_2002_43_3_a14/
%G en
%F CMUC_2002_43_3_a14
Brešar, Boštjan; Klavžar, Sandi. On partial cubes and graphs with convex intervals. Commentationes Mathematicae Universitatis Carolinae, Tome 43 (2002) no. 3, pp. 537-545. http://geodesic.mathdoc.fr/item/CMUC_2002_43_3_a14/