Na Oddelku za matematiko in računalništvo je doktoriral Iztok Peterin. Naslov doktorske disertacije je Nekatere faktorizacije v metrični teoriji grafov. Opravljena je bila pod mentorskim vodstvom prof. dr. Sandija Klavžarja in somentorja prof. dr. Wilfrieda Imricha iz Univerze v Leobnu. Komisijo za zagovor sta dopolnjevala še prof. dr. Boštjan Brešar in prof. dr. Aleksander Vesel.
Doktorska disertacija obravnava faktorizacije grafov glede na kartezični produkt grafov, kjer (po)iščemo razbitje množice povezav na take podmnožice, da so v vsaki podmnožici povezave, ki pripadajo istemu faktorju. Takšno razbitje nam na naraven način vloži graf v kartezični produkt kvocientnih grafov porojenih z prej omenjenim razbitjem.
Predstavljeni so zadostni in potrebni pogoji, ki jih mora vsebovati razbitje množice povezav, da je graf podgraf poljubnega kartezičnega produkta, podgraf Hammingovega grafa, induciran podgraf kartezičnega produkta, induciran podgraf Hammingovega grafa, izometričen podgraf Hammingovega grafa, zastavni graf in ravninski medianski graf.
Predstavljen je tudi linearni algoritem za prafaktorizacijo grafa glede na kartezični produkt. Le-ta algoritem je optimalen glede časovne zahtevnosti in predstavlja zaključek 20 let trajajočega razvoja na tem področju.
Predstavljeni so zadostni in potrebni pogoji, ki jih mora vsebovati razbitje množice povezav, da je graf podgraf poljubnega kartezičnega produkta, podgraf Hammingovega grafa, induciran podgraf kartezičnega produkta, induciran podgraf Hammingovega grafa, izometričen podgraf Hammingovega grafa, zastavni graf in ravninski medianski graf.
Predstavljen je tudi linearni algoritem za prafaktorizacijo grafa glede na kartezični produkt. Le-ta algoritem je optimalen glede časovne zahtevnosti in predstavlja zaključek 20 let trajajočega razvoja na tem področju.
To je štirinajsti doktorat iz matematike na našem oddelku.
