20.500.12556/DKUM-51591 Maximal proper subgraphs of median graphs Maksimalni pravi podgrafi medianskih grafov Za medianski graf ▫$G$▫ in vozlišče ▫$v$▫, ki ni presečno, dokažemo, da je ▫$G-v$▫ medianski graf natanko tedaj, ko ▫$v$▫ ni center dvodelnega kolesa. To je nadalje ekvivalentno obstoju določene eliminacijske sheme za povezave, ki so incidenčne z ▫$v$▫. Rezultat implicira karakterizacijo po vozliščih kritičnih (po vozliščih polnih) medianskih grafov, ki so medianski grafi, katerih vsi podgrafi brez enega vozlišča niso medianski (so medianski). Podani sta tudi dve analogni karakterizaciji za primer odstranjevanja povezav. For a median graph ▫$G$▫ and a vertex ▫$v$▫ of ▫$G$▫ that is not a cut-vertex we show that ▫$G-v$▫ is a median graph precisely when v is not the center of a bipartite wheel, which is in turn equivalent with the existence of a certain edge elimination scheme for edges incident with ▫$v$▫. This implies a characterization of vertex-critical (respectively, vertex-complete) median graphs, which are median graphs whose all vertex-deleted subgraphs are not median (respectively, are median). Moreover, two analogous characterizations for edge-deleted median graphs are given. matematika teorija grafov medianski graf podgraf brez enega vozlišča dvodelno kolo kvadratna povezava mathematics graph theory median graph vertex-deleted subgraph bipartite wheel square-eddge square-dismantlable vertex true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 14:57:10 2015-07-10 14:57:10 2022-05-30 03:06:31 2019-07-11 07:23:03 2007 0 0 str. 1389-1394 iss. 11-12 Vol. 307 2007 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 1118479 14257497 0012-365X URN:SI:UM:DK:CX54VZBS http://dx.doi.org/10.1016/j.disc.2005.11.076 1 https://dk.um.si/Dokument.php?lang=slv&id=76151 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0