20.500.12556/DKUM-91119 Efficient proper embedding of a daisy cube Učinkovita pravilna vložitev marjetične kocke For a set ▫$X$▫ of binary words of length ▫$h$▫ the daisy cube ▫$Q_h(X)$▫ is defined as the subgraph of the hypercube ▫$Q_h$▫ induced by the set of all vertices on shortest paths that connect vertices of ▫$X$▫ with the vertex ▫$0^h$▫. A vertex in the intersection of all of these paths is a minimal vertex of a daisy cube. A graph ▫$G$▫ isomorphic to a daisy cube admits several isometric embeddings into a hypercube. We show that an isometric embedding is proper if and only if the label ▫$0^h$▫ is assigned to a minimal vertex of ▫$G$▫. This result allows us to devise an algorithm which finds a proper embedding of a graph isomorphic to a daisy cube into a hypercube in linear time. Če je ▫$X$▫ neka množica binarnih besed dolžine ▫$h$▫, potem je marjetična kocka ▫$Q_h(X)$▫ definirana kot podgraf hiperkocke ▫$Q_h$▫, induciran z množico vseh točk na najkrajših poteh, ki povezujejo točke množice ▫$X$▫ s točko ▫$0^h$▫. Točka v preseku vseh teh poti je minimalna točka marjetične kocke. Graf ▫$G$▫, izomorfen marjetični kocki, ima več izometričnih vložitev v hiperkocko. Pokažemo, da je izometrična vložitev pravilna natanko tedaj, ko je oznaka ▫$0^h$▫ pripisana minimalni točki grafa ▫$G$▫. Na osnovi tega rezultata razvijemo algoritem, ki poišče pravilno vložitev grafa, izomorfnega marjetični kocki, v hiperkocko, in to v linearnem času. daisy cube partial cube isometric embedding proper embedding marjetična kocka delna kocka izometrična vložitev pravilna vložitev true true true Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije Angleški jezik Slovenski jezik Znanstveno delo 2024-11-08 03:07:20 2024-11-29 14:48:09 2024-11-30 03:14:34 0000-00-00 00:00:00 2021 0 Koper 0 str. 271-282 št. 2 Letn. 21 2021 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2021-10-25 519.17 72352259 10.26493/1855-3974.2454.892 1855-3966 RAZ_Vesel_Aleksander_2021.pdf RAZ_Vesel_Aleksander_2021.pdf 1 A174426B26434A2E5A542E7F9F45B11A ef0a6c829a6336fccbc56b450e7175117bbbf33b2d0515fce0cfce20cffe8e09 18e854ed-ae58-11ef-8753-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=187038 https://amc-journal.eu/index.php/amc/article/download/2454/1711 1 2fef05f2-9d76-11ef-847f-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=186803 Fakulteta za naravoslovje in matematiko 0 0 0