# 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

## Access Full Article

top## Abstract

top## How to cite

topBostjan 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] 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] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407. Zbl0551.05060
- [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] 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] 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] 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] 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] B. Brešar, S. Klavžar, R. Skrekovski, Cubes polynomial and its derivatives, Electron. J. Combin. 10 (2003) #R3, pp. 11. Zbl1020.05035
- [9] V. Chepoi, d-Convexity and isometric subgraphs of Hamming graphs, Cybernetics 1 (1988) 6-10, doi: 10.1007/BF01069520.
- [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] 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] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938) 239-250. Zbl0020.07804
- [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] 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] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (John Wiley & Sons, New York, 2000).
- [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] 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] 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] 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] H.M. Mulder, n-Cubes and median graphs, J. Graph Theory 4 (1980) 107-110, doi: 10.1002/jgt.3190040112. Zbl0427.05046
- [21] H.M. Mulder, The Interval Function of a Graph, (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980). Zbl0446.05039
- [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] 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] 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] 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] R. Skrekovski, Two relations for median graphs, Discrete Math. 226 (2001) 351-353, doi: 10.1016/S0012-365X(00)00120-5. Zbl0958.05043
- [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] 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] 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

## Citations in EuDML Documents

top## NotesEmbed ?

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