Tree-like isometric subgraphs of hypercubes

Bostjan Brešar; Wilfried Imrich; Sandi Klavžar

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 227-240
  • ISSN: 2083-5892

Abstract

top
Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.

How to cite

top

Bostjan Brešar, Wilfried Imrich, and Sandi Klavžar. "Tree-like isometric subgraphs of hypercubes." Discussiones Mathematicae Graph Theory 23.2 (2003): 227-240. <http://eudml.org/doc/270257>.

@article{BostjanBrešar2003,
abstract = {Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.},
author = {Bostjan Brešar, Wilfried Imrich, Sandi Klavžar},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {isometric embeddings; partial cubes; expansion procedures; trees; median graphs; graph automorphisms; automorphism groups; dismantlable graphs; tree-like partial cubes; open problems},
language = {eng},
number = {2},
pages = {227-240},
title = {Tree-like isometric subgraphs of hypercubes},
url = {http://eudml.org/doc/270257},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Bostjan Brešar
AU - Wilfried Imrich
AU - Sandi Klavžar
TI - Tree-like isometric subgraphs of hypercubes
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 227
EP - 240
AB - Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph of a tree-like partial cube is dismantlable. This in particular implies that every tree-like partial cube G contains a cube that is invariant under every automorphism of G. We also show that weak retractions preserve tree-like partial cubes, which in turn implies that every contraction of a tree-like partial cube fixes a cube. The paper ends with several Frucht-type results and a list of open problems.
LA - eng
KW - isometric embeddings; partial cubes; expansion procedures; trees; median graphs; graph automorphisms; automorphism groups; dismantlable graphs; tree-like partial cubes; open problems
UR - http://eudml.org/doc/270257
ER -

References

top
  1. [1] F. Aurenhammer and J. Hagauer, Recognizing binary Hamming graphs in O(n²log n) time, Math. Systems Theory 28 (1995) 387-396, doi: 10.1007/BF01185863. Zbl0833.68087
  2. [2] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407. Zbl0551.05060
  3. [3] H.-J. Bandelt and E. Prisner, Clique graphs and Helly graphs, J. Combin. Theory (B) 51 (1991) 34-45, doi: 10.1016/0095-8956(91)90004-4. Zbl0726.05060
  4. [4] H.-J. Bandelt, M. van de Vel, A fixed cube theorem for median graphs, Discrete Math. 62 (1987) 129-137, doi: 10.1016/0012-365X(87)90022-7. Zbl0628.05053
  5. [5] H.-J. Bandelt and M. van de Vel, Superextensions and the depth of median graphs, J. Combin. Theory (A) 57 (1991) 187-202, doi: 10.1016/0097-3165(91)90044-H. Zbl0756.05091
  6. [6] B. Brešar, W. Imrich and S. Klavžar, Fast recognition algorithms for classes of partial cubes, Discrete Appl. Math., in press. Zbl1022.05050
  7. [7] B. Brešar, W. Imrich, S. Klavžar, H.M. Mulder and R. Skrekovski, Tiled partial cubes, J. Graph Theory 40 (2002) 91-103, doi: 10.1002/jgt.10031. 
  8. [8] B. Brešar, S. Klavžar, R. Skrekovski, Cubes polynomial and its derivatives, Electron. J. Combin. 10 (2003) #R3, pp. 11. Zbl1020.05035
  9. [9] V. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-10, doi: 10.1007/BF01069520. 
  10. [10] V. Chepoi, Bridged graphs are cop-win graphs: an algorithmic proof, J. Combin. Theory (B) 69 (1997) 97-100, doi: 10.1006/jctb.1996.1726. Zbl0873.05060
  11. [11] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. Zbl0245.05113
  12. [12] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938) 239-250. Zbl0020.07804
  13. [13] J. Hagauer, W. Imrich and S. Klavžar, Recognizing median graphs in subquadratic time, Theoret. Comput. Sci. 215 (1999) 123-136, doi: 10.1016/S0304-3975(97)00136-9. Zbl0913.68152
  14. [14] W. Imrich and S. Klavžar, A convexity lemma and expansion procedures for bipartite graphs, European J. Combin. 19 (1998) 677-685, doi: 10.1006/eujc.1998.0229. Zbl0918.05085
  15. [15] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000). 
  16. [16] W. Imrich, S. Klavžar, and H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12 (1999) 111-118, doi: 10.1137/S0895480197323494. Zbl0916.68106
  17. [17] S. Klavžar and A. Lipovec, Partial cubes as subdivision graphs and as generalized Petersen graphs, Discrete Math. 263 (2003) 157-165, doi: 10.1016/S0012-365X(02)00575-7. Zbl1014.05064
  18. [18] S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127. Zbl0931.05072
  19. [19] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1. Zbl0394.05038
  20. [20] H.M. Mulder, n-Cubes and median graphs, J. Graph Theory 4 (1980) 107-110, doi: 10.1002/jgt.3190040112. Zbl0427.05046
  21. [21] H.M. Mulder, The Interval Function of a Graph, (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
  22. [22] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477. Zbl0744.05064
  23. [23] R. Nowakowski and I. Rival, Fixed-edge theorem for graphs with loops, J. Graph Theory 3 (1979) 339-350, doi: 10.1002/jgt.3190030404. 
  24. [24] R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Math. 43 (1983) 235-239, doi: 10.1016/0012-365X(83)90160-7. Zbl0508.05058
  25. [25] G. Sabidussi, Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957) 515-525, doi: 10.4153/CJM-1957-060-7. Zbl0079.39202
  26. [26] R. Skrekovski, Two relations for median graphs, Discrete Math. 226 (2001) 351-353, doi: 10.1016/S0012-365X(00)00120-5. Zbl0958.05043
  27. [27] P.S. Soltan and V. Chepoi, Solution of the Weber problem for discrete median metric spaces, (Russian) Trudy Tbiliss. Mat. Inst. Razmadze Akad. Nauk Gruzin. SSR 85 (1987) 52-76. 
  28. [28] C. Tardif, Prefibers and the Cartesian product of metric spaces, Discrete Math. 109 (1992) 283-288, doi: 10.1016/0012-365X(92)90298-T. Zbl0777.05097
  29. [29] P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6. Zbl0529.05055

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.