| Naslov: | Tree-like isometric subgraphs of hypercubes |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Imrich, Wilfried (Avtor)
ID Klavžar, Sandi (Avtor) |
|---|
| Datoteke: |  Discussiones_Mathematicae_Graph_Theory_2003_Bresar,_Imrich,_Klavzar_Tree-like_isometric_subgraphs_of_hypercubes.pdf (135,80 KB)
MD5: EA9AE3B5ECBCA8360FB1E524BAC7DB89
 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1199
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Neznano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
|
|---|
| Opis: | Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we 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 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. |
|---|
| Ključne besede: | mathematics, graph theory, Isometric embeddings, partial cubes, expansion procedures, trees, median graphs, graph automorphisms, automorphism groups, dismantlable graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2003 |
|---|
| Št. strani: | str. 227-240 |
|---|
| Številčenje: | Letn. 23, št. 2 |
|---|
| PID: | 20.500.12556/DKUM-65355  |
|---|
| ISSN: | 1234-3099 |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 12621145 |
|---|
| ISSN pri članku: | 1234-3099 |
|---|
| NUK URN: | URN:SI:UM:DK:MQ8H6RU7 |
|---|
| Datum objave v DKUM: | 31.03.2017 |
|---|
| Število ogledov: | 1981 |
|---|
| Število prenosov: | 454 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
