20.500.12556/DKUM-65334 Arboreal structure and regular graphs of median-like classes Drevesna struktura in regularni grafi razredov grafov sorodnih medianskim grafom We consider classes of graphs that enjoy the following properties: they are closed for gated subgraphs, gated amalgamation and Cartesian products, and for any gated subgraph the inverse of gate function maps vertices to gated subsets. We prove that any graph of such a class contains a peripheral subgraph which is a Cartesian product of two graphs: a gated subgraph and a prime graph minus a vertex. Therefore, these graphs admit a peripheral elimination procedure which is a generalization of analogous procedure in median graphs. We characterize regular graphs of these classes whenever they enjoy an additional properties. As a corollary we derive that regular weakly median graphs are precisely Cartesian products in which each factor is a complete graph or a hyperoctahedron. V članku so obravnavani razredi grafov, ki so zaprti za zastražene podgrafe, zastraženo amalgamacijo in kartezične produkte, ter zadoščajo še naslednji lastnosti: za vsak zastražen podgraf grafa tega razreda inverzna funkcija zastraženostne funkcije slika točke v zastražene podmnožice. Dokazano je, da vsak graf takega razreda vsebuje periferen podgraf, ki je kartezični produkt dveh grafov: zastraženega podgrafa danega grafa in pragrafa brez ene točke. Potemtakem za te grafe obstaja periferni eliminacijski postopek, ki je posplošitev analognega postopka na medianskih grafih. Podana je karakterizacija regularnih grafov teh razredov v primeru, ko razredi zadoščajo dodatni lastnosti. Posledično je izpeljano, da so regularni šibko medianski grafi natanko kartezični produkti, v katerih je vsak faktor bodisi poln graf bodisi hiperoktaeder. mathematics graph theory median graph tree gatedness amalgam periphery regular graph matematika teorija grafov medianski graf drevo zastraženost amalgam periferija regularen graf true true true Angleški jezik Slovenski jezik Neznano 2017-03-31 10:02:24 2017-03-31 10:03:11 2022-07-08 03:07:35 2019-07-11 15:14:54 2003 0 0 str. 215-225 š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 12602713 1234-3099 URN:SI:UM:DK:TLVY6BWE Discussiones_Mathematicae_Graph_Theory_2003_Bresar_Arboreal_structure_and_regular_graphs_of_median-like_classes.pdf Discussiones_Mathematicae_Graph_Theory_2003_Bresar_Arboreal_structure_and_regular_graphs_of_median-like_classes.pdf 1 90ED56DF748C8B8B97D4BD9C18DF3C11 d6497d09c19301050de05a5e27e2dab914364332b5a6f0ac06902f13db81ab78 0b39304a-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110392 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1198 1 https://dk.um.si/Dokument.php?lang=slv&id=110391 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0