On partial cubes and graphs with convex intervals
Brešar, Boštjan ; Klavžar, Sandi
Commentationes Mathematicae Universitatis Carolinae, Tome 43 (2002), p. 537-545 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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$.

Publié le : 2002-01-01
Classification:  05C12,  05C75 
@article{119344,
     author = {Bo\v stjan Bre\v sar and Sandi Klav\v zar},
     title = {On partial cubes and graphs with convex intervals},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {43},
     year = {2002},
     pages = {537-545},
     zbl = {1090.05023},
     mrnumber = {1920530},
     language = {en},
     url = {http://dml.mathdoc.fr/item/119344}
}

Brešar, Boštjan; Klavžar, Sandi. On partial cubes and graphs with convex intervals. Commentationes Mathematicae Universitatis Carolinae, Tome 43 (2002) pp. 537-545. http://gdmltest.u-ga.fr/item/119344/

Aurenhammer F.; Formann M.; Idury R.; Schäffer A.; Wagner F. Faster isometric embeddings in products of complete graphs, Discrete Appl. Math. 52 (1994), 17-28. (1994) | MR 1283241

Aurenhammer F.; Hagauer J. Recognizing binary Hamming graphs in $O(n^2 \log n)$ time, Math. Systems Theory 28 (1995), 387-395. (1995) | MR 1371084

Avis D. Hypermetric spaces and the Hamming cone, Canad. J. Math. 33 (1981), 795-802. (1981) | MR 0634138 | Zbl 0445.52008

Chepoi V. $d$-convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988), 6-9. (1988) | MR 0939233

Chepoi V. On distances in benzenoid graphs, J. Chem. Inform. Comput. Sci. 36 (1996), 1169-1172. (1996)

Chepoi V.; Klavžar S. The Wiener index and the Szeged index of benzenoid systems in linear time, J. Chem. Inform. Comput. Sci. 37 (1997), 752-755. (1997)

Chepoi V.; Tardif C. personal communication, 1994.

Djoković D. Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973), 263-267. (1973) | MR 0314669

Fukuda K.; Handa K. Antipodal graphs and oriented matroids, Discrete Math. 111 (1993), 245-256. (1993) | MR 1210100 | Zbl 0782.05069

Graham R.L.; Pollak H. On addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495-2519. (1971) | MR 0289210

Imrich W.; Klavžar S. On the complexity of recognizing Hamming graphs and related classes of graphs, European J. Combin. 17 (1996), 209-221. (1996) | MR 1379372

Imrich W.; Klavžar S. A convexity lemma and expansion procedures for bipartite graphs, European J. Combin. 19 (1998), 677-685. (1998) | MR 1642702

Imrich W.; Klavžar S. Product Graphs: Structure and Recognition, Wiley, New York, 2000. | MR 1788124

Klavžar S.; Gutman I. Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997), 73-81. (1997) | MR 1489061

Lawrence J. Lopsided sets and orthant-intersection by convex sets, Pacific J. Math. 104 (1983), 155-173. (1983) | MR 0683734 | Zbl 0471.52003

Mollard M. Interval-regularity does not lead to interval monotonicity, Discrete Math. 118 (1993), 233-237. (1993) | MR 1230065 | Zbl 0784.05040

Mulder H.M. The Interval Function of a Graph, Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. | MR 0605838

Wilkeit E. Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B 50 (1990), 179-197. (1990) | MR 1081222 | Zbl 0657.05023

Winkler P. Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984), 221-225. (1984) | MR 0727925