20.500.12556/DKUM-65355 Tree-like isometric subgraphs of hypercubes Drevesom podobni izometrični podgrafi hiperkock 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. 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. mathematics graph theory Isometric embeddings partial cubes expansion procedures trees median graphs graph automorphisms automorphism groups dismantlable graphs matematika teorija grafov izometrične vložitve delne kocke drevesa ekspanzija medianski grafi avtomorfizmi grafov grupe avtomorfizmov odstranljivi grafi true true true Angleški jezik Slovenski jezik Neznano 2017-03-31 14:39:34 2017-03-31 14:40:34 2022-07-08 03:07:43 2019-07-11 15:11:03 2003 0 0 str. 227-240 št. 2 Letn. 23 2003 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1234-3099 519.17 7487065 12621145 1234-3099 URN:SI:UM:DK:MQ8H6RU7 Discussiones_Mathematicae_Graph_Theory_2003_Bresar,_Imrich,_Klavzar_Tree-like_isometric_subgraphs_of_hypercubes.pdf Discussiones_Mathematicae_Graph_Theory_2003_Bresar,_Imrich,_Klavzar_Tree-like_isometric_subgraphs_of_hypercubes.pdf 1 EA9AE3B5ECBCA8360FB1E524BAC7DB89 6825956cb896a2451816c4393a4a54b1e0738d71505148af944d0cacc308a02c 0c22f19b-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110438 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1199 1 https://dk.um.si/Dokument.php?lang=slv&id=110437 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0