On cube-free median graphsBrešar, Boštjan (Avtor) Klavžar, Sandi (Avtor) Škrekovski, Riste (Avtor) matematikateorija grafovmedianski grafkartezični produktprepoznavni algoritemmathematicsgraph theorymedian graphcube-free graphCartesian productrecognition algoritemNaj bo ▫$G$▫ mediansk graf brez 3-kocke. Pokazano je, da velja ▫$frac{k}{2} ge sqrt{n}-1 ge frac{m}{2sqrt{n}} ge sqrt{s} ge r-1$▫, kjer so ▫$n, m, s, k$▫ in ▫$r$▫ števila točk, povezav, kvadratov, ▫$Theta$▫-razredov in število povezav najmanšega ▫$Theta$▫-razreda grafa ▫$G$▫. Enakosti so dosežene natanko tedaj, ko je ▫$G$▫ kartezični produkt dveh dreves istega reda. Obravnavan je tudi polinom kock medianskih grafov in pokazano je, da lahko ravninske medianske grafe brez 3-kocke prepoznamo v linearnem času.20032015-07-10 11:58:53Delo ni kategorizirano49368sl