Tree-like isometric subgraphs of hypercubes

Boštjan Brešar (Author), Wilfried Imrich (Author), Sandi Klavžar (Author)

Abstract

Drevesom podobni podgrafi hiperkock predstavljajo posplošitev medianskih grafov. Tako kot medianski grafi podedujejo veliko lastnosti dreves, toda lahko vsebujejo večje razrede grafov, ki jih morda lahko hitreje prepoznamo kot medianske grafe. V članku proučujemo strukturo drevesom podobnih delnih kock, jih karakteriziramo in predstavimo primere podobnosti z drevesi in medianskimi grafi. Na primer, dokažemo, da so grafi kock drevesom podobnih delnih kock odstranljivi grafi. To med drugim implicira, da vsaka drevesom podobna delna kocka ▫$G$▫ vsebuje kocko, ki je invarianta za vse avtomorfizme ▫$G$▫. Dokažemo tudi, da je vsaka šibka retrakcija takih grafov spet drevesom podobna delna kocka. Članek je zaključen z nekaj rezultati Fruchtovega tipa in s seznamov odprtih problemov.

Keywords

matematika;teorija grafov;izometrične vložitve;delne kocke;drevesa;ekspanzija;medianski grafi;avtomorfizmi grafov;grupe avtomorfizmov;odstranljivi grafi;mathematics;graph theory;Isometric embeddings;partial cubes;expansion procedures;trees;median graphs;graph automorphisms;automorphism groups;dismantlable graphs;

Data

Language:	English
Year of publishing:	2003
Typology:	1.01 - Original Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17
COBISS:	12621145
ISSN:	1234-3099
Views:	1007
Downloads:	318
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Drevesom podobni izometrični podgrafi hiperkock
Secondary abstract:	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.
Secondary keywords:	matematika;teorija grafov;izometrične vložitve;delne kocke;drevesa;ekspanzija;medianski grafi;avtomorfizmi grafov;grupe avtomorfizmov;odstranljivi grafi;
URN:	URN:SI:UM:
Type (COBISS):	Scientific work
Pages:	str. 227-240
Volume:	ǂVol. ǂ23
Issue:	ǂno. ǂ2
Chronology:	2003
ID:	9595924