Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions
isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions
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$.
References:
[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
[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
[3] Avis D.: Hypermetric spaces and the Hamming cone. Canad. J. Math. 33 (1981), 795-802. MR 0634138 | Zbl 0445.52008
[4] Chepoi V.: $d$-convexity and isometric subgraphs of Hamming graphs. Cybernetics 1 (1988), 6-9. MR 0939233
[5] Chepoi V.: On distances in benzenoid graphs. J. Chem. Inform. Comput. Sci. 36 (1996), 1169-1172.
[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.
[7] Chepoi V., Tardif C.: personal communication. 1994.
[8] Djoković D.: Distance preserving subgraphs of hypercubes. J. Combin. Theory Ser. B 14 (1973), 263-267. MR 0314669
[9] Fukuda K., Handa K.: Antipodal graphs and oriented matroids. Discrete Math. 111 (1993), 245-256. MR 1210100 | Zbl 0782.05069
[10] Graham R.L., Pollak H.: On addressing problem for loop switching. Bell System Tech. J. 50 (1971), 2495-2519. MR 0289210
[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
[12] Imrich W., Klavžar S.: A convexity lemma and expansion procedures for bipartite graphs. European J. Combin. 19 (1998), 677-685. MR 1642702
[13] Imrich W., Klavžar S.: Product Graphs: Structure and Recognition. Wiley, New York, 2000. MR 1788124
[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
[15] Lawrence J.: Lopsided sets and orthant-intersection by convex sets. Pacific J. Math. 104 (1983), 155-173. MR 0683734 | Zbl 0471.52003
[16] Mollard M.: Interval-regularity does not lead to interval monotonicity. Discrete Math. 118 (1993), 233-237. MR 1230065 | Zbl 0784.05040
[17] Mulder H.M.: The Interval Function of a Graph. Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. MR 0605838
[18] Wilkeit E.: Isometric embeddings in Hamming graphs. J. Combin. Theory Ser. B 50 (1990), 179-197. MR 1081222 | Zbl 0657.05023
[19] Winkler P.: Isometric embeddings in products of complete graphs. Discrete Appl. Math. 7 (1984), 221-225. MR 0727925
Search
Partner of
