- Tytuł:
- Tree-like isometric subgraphs of hypercubes
- Autorzy:
-
Brešar, Bostjan
Imrich, Wilfried
Klavžar, Sandi - Powiązania:
- https://bibliotekanauki.pl/articles/743405.pdf
- Data publikacji:
- 2003
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
isometric embeddings
partial cubes
expansion procedures
trees
median graphs
graph automorphisms
automorphism groups
dismantlable graphs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 227-240
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł