Maximal proper subgraphs of median graphsBrešar, Boštjan (Avtor) Klavžar, Sandi (Avtor) matematikateorija grafovmedianski grafpodgraf brez enega vozliščadvodelno kolokvadratna povezavamathematicsgraph theorymedian graphvertex-deleted subgraphbipartite wheelsquare-eddgesquare-dismantlable vertexZa 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.20072015-07-10 14:57:10Delo ni kategorizirano51591sl