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/