| Title:
|
On partial cubes and graphs with convex intervals (English) |
| Author:
|
Brešar, Boštjan |
| Author:
|
Klavžar, Sandi |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
43 |
| Issue:
|
3 |
| Year:
|
2002 |
| Pages:
|
537-545 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
isometric embeddings |
| Keyword:
|
hypercubes |
| Keyword:
|
partial cubes |
| Keyword:
|
convex intervals |
| Keyword:
|
subdivisions |
| MSC:
|
05C12 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 1090.05023 |
| idMR:
|
MR1920530 |
| . |
| Date available:
|
2009-01-08T19:24:58Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119344 |
| . |
| Reference:
|
[1] 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. MR 1283241 |
| Reference:
|
[2] Aurenhammer F., Hagauer J.: Recognizing binary Hamming graphs in $O(n^2 \log n)$ time.Math. Systems Theory 28 (1995), 387-395. MR 1371084 |
| Reference:
|
[3] Avis D.: Hypermetric spaces and the Hamming cone.Canad. J. Math. 33 (1981), 795-802. Zbl 0445.52008, MR 0634138 |
| Reference:
|
[4] Chepoi V.: $d$-convexity and isometric subgraphs of Hamming graphs.Cybernetics 1 (1988), 6-9. MR 0939233 |
| Reference:
|
[5] Chepoi V.: On distances in benzenoid graphs.J. Chem. Inform. Comput. Sci. 36 (1996), 1169-1172. |
| Reference:
|
[6] 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. |
| Reference:
|
[7] Chepoi V., Tardif C.: personal communication.1994. |
| Reference:
|
[8] Djoković D.: Distance preserving subgraphs of hypercubes.J. Combin. Theory Ser. B 14 (1973), 263-267. MR 0314669 |
| Reference:
|
[9] Fukuda K., Handa K.: Antipodal graphs and oriented matroids.Discrete Math. 111 (1993), 245-256. Zbl 0782.05069, MR 1210100 |
| Reference:
|
[10] Graham R.L., Pollak H.: On addressing problem for loop switching.Bell System Tech. J. 50 (1971), 2495-2519. MR 0289210 |
| Reference:
|
[11] Imrich W., Klavžar S.: On the complexity of recognizing Hamming graphs and related classes of graphs.European J. Combin. 17 (1996), 209-221. MR 1379372 |
| Reference:
|
[12] Imrich W., Klavžar S.: A convexity lemma and expansion procedures for bipartite graphs.European J. Combin. 19 (1998), 677-685. MR 1642702 |
| Reference:
|
[13] Imrich W., Klavžar S.: Product Graphs: Structure and Recognition.Wiley, New York, 2000. MR 1788124 |
| Reference:
|
[14] Klavžar S., Gutman I.: Wiener number of vertex-weighted graphs and a chemical application.Discrete Appl. Math. 80 (1997), 73-81. MR 1489061 |
| Reference:
|
[15] Lawrence J.: Lopsided sets and orthant-intersection by convex sets.Pacific J. Math. 104 (1983), 155-173. Zbl 0471.52003, MR 0683734 |
| Reference:
|
[16] Mollard M.: Interval-regularity does not lead to interval monotonicity.Discrete Math. 118 (1993), 233-237. Zbl 0784.05040, MR 1230065 |
| Reference:
|
[17] Mulder H.M.: The Interval Function of a Graph.Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. MR 0605838 |
| Reference:
|
[18] Wilkeit E.: Isometric embeddings in Hamming graphs.J. Combin. Theory Ser. B 50 (1990), 179-197. Zbl 0657.05023, MR 1081222 |
| Reference:
|
[19] Winkler P.: Isometric embeddings in products of complete graphs.Discrete Appl. Math. 7 (1984), 221-225. MR 0727925 |
| . |
