Relations between median graphs, semi-median graphs and partial cubesImrich, Wilfried (Avtor) Klavžar, Sandi (Avtor) Mulder, Henry Martyn (Avtor) Škrekovski, Riste (Avtor) matematikateorija grafovmedianski grafidelne kockesemi-medianski grafimathematicsgraph theorymedian graphspartial cubessemi median graphsPodan je samostojen dokaz ekspanzijskega izreka za semi-medianske grafe. Dokazano je, da te grafe lahko karakteriziramo kot tlakovane delne kocke in da za njih velja neenakost ▫$2n-m-k le 2$▫. Pri tem je ▫$k$▫ število ekvivalenčnih razredov relacije ▫$Theta$▫. Za medianske grafe dokažemo, da se dajo karakterizirati kot semi-medianski grafi brez ▫$Q_3^-$▫. Vpeljemo tudi koncept šibke 2-konveksnosti in jo uporabimo, med drugim, za dokaz, da so medianski grafi dvodelni grafi, ki zadoščajo šibki 2-konveksnosti intervalov in štirikotniški lastnosti.19982015-07-10 11:55:38Delo ni kategorizirano49362ISSN: 1318-4865UDK: 519.17OceCobissID: 44310272COBISS_ID: 8227417NUK URN: URN:SI:UM:DK:DQ6Y4LLZsl