On partial cubes and graphs with convex intervals

Boštjan Brešar; Sandi Klavžar

Commentationes Mathematicae Universitatis Carolinae (2002)

  • Volume: 43, Issue: 3, page 537-545
  • ISSN: 0010-2628

Abstract

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

How to cite

top

Brešar, Boštjan, and Klavžar, Sandi. "On partial cubes and graphs with convex intervals." Commentationes Mathematicae Universitatis Carolinae 43.3 (2002): 537-545. <http://eudml.org/doc/249012>.

@article{Brešar2002,
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$.},
author = {Brešar, Boštjan, Klavžar, Sandi},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions; isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions},
language = {eng},
number = {3},
pages = {537-545},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {On partial cubes and graphs with convex intervals},
url = {http://eudml.org/doc/249012},
volume = {43},
year = {2002},
}

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
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 43
IS - 3
SP - 537
EP - 545
AB - 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$.
LA - eng
KW - isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions; isometric embeddings; hypercubes; partial cubes; convex intervals; subdivisions
UR - http://eudml.org/doc/249012
ER -

References

top
  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. (1994) MR1283241
  2. Aurenhammer F., Hagauer J., Recognizing binary Hamming graphs in O ( n 2 log n ) time, Math. Systems Theory 28 (1995), 387-395. (1995) MR1371084
  3. Avis D., Hypermetric spaces and the Hamming cone, Canad. J. Math. 33 (1981), 795-802. (1981) Zbl0445.52008MR0634138
  4. Chepoi V., d -convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988), 6-9. (1988) MR0939233
  5. Chepoi V., On distances in benzenoid graphs, J. Chem. Inform. Comput. Sci. 36 (1996), 1169-1172. (1996) 
  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. (1997) 
  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. (1973) MR0314669
  9. Fukuda K., Handa K., Antipodal graphs and oriented matroids, Discrete Math. 111 (1993), 245-256. (1993) Zbl0782.05069MR1210100
  10. Graham R.L., Pollak H., On addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495-2519. (1971) MR0289210
  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. (1996) MR1379372
  12. Imrich W., Klavžar S., A convexity lemma and expansion procedures for bipartite graphs, European J. Combin. 19 (1998), 677-685. (1998) MR1642702
  13. Imrich W., Klavžar S., Product Graphs: Structure and Recognition, Wiley, New York, 2000. MR1788124
  14. Klavžar S., Gutman I., Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997), 73-81. (1997) MR1489061
  15. Lawrence J., Lopsided sets and orthant-intersection by convex sets, Pacific J. Math. 104 (1983), 155-173. (1983) Zbl0471.52003MR0683734
  16. Mollard M., Interval-regularity does not lead to interval monotonicity, Discrete Math. 118 (1993), 233-237. (1993) Zbl0784.05040MR1230065
  17. Mulder H.M., The Interval Function of a Graph, Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980. MR0605838
  18. Wilkeit E., Isometric embeddings in Hamming graphs, J. Combin. Theory Ser. B 50 (1990), 179-197. (1990) Zbl0657.05023MR1081222
  19. Winkler P., Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984), 221-225. (1984) MR0727925

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.