Geodesic
Tree-like isometric subgraphs of hypercubes
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 227-240.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs 
@article{DMGT_2003_23_2_a2,
     author = {Bre\v{s}ar, Bostjan and Imrich, Wilfried and Klav\v{z}ar, Sandi},
     title = {Tree-like isometric subgraphs of hypercubes},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {227--240},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a2/}
}
TY  - JOUR
AU  - Brešar, Bostjan
AU  - Imrich, Wilfried
AU  - Klavžar, Sandi
TI  - Tree-like isometric subgraphs of hypercubes
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 227
EP  - 240
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a2/
LA  - en
ID  - DMGT_2003_23_2_a2
ER  - 
%0 Journal Article
%A Brešar, Bostjan
%A Imrich, Wilfried
%A Klavžar, Sandi
%T Tree-like isometric subgraphs of hypercubes
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 227-240
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a2/
%G en
%F DMGT_2003_23_2_a2
Brešar, Bostjan; Imrich, Wilfried; Klavžar, Sandi. Tree-like isometric subgraphs of hypercubes. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 227-240. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a2/

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

[2] H.-J. Bandelt, Retracts of hypercubes, J. Graph Theory 8 (1984) 501-510, doi: 10.1002/jgt.3190080407.

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

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

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

[6] B. Brešar, W. Imrich and S. Klavžar, Fast recognition algorithms for classes of partial cubes, Discrete Appl. Math., in press.

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

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

[11] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5.

[12] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math. 6 (1938) 239-250.

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

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

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

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

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

[19] H.M. Mulder, The structure of median graphs, Discrete Math. 24 (1978) 197-204, doi: 10.1016/0012-365X(78)90199-1.

[20] H.M. Mulder, n-Cubes and median graphs, J. Graph Theory 4 (1980) 107-110, doi: 10.1002/jgt.3190040112.

[21] H.M. Mulder, The Interval Function of a Graph, (Mathematical Centre Tracts 132, Mathematisch Centrum, Amsterdam, 1980).

[22] H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek (ed.), Contemporary Methods in Graph Theory (Wissenschaftsverlag, Mannheim, 1990) 459-477.

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

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

[26] R. Skrekovski, Two relations for median graphs, Discrete Math. 226 (2001) 351-353, doi: 10.1016/S0012-365X(00)00120-5.

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

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