Na Oddelku za matematiko in računalništvo je doktoriral Aleksander Kelenc.
Naslov doktorske disertacije je Distance-based invariants and measures in graphs (Na razdaljah osnovane invariante in mere v grafih). Opravljena je bila pod mentorstvom doc. dr. Andreja Taranenka in somentorstvom izr. prof. dr. Ismaela Gonzalez Yera, komisijo pa so poleg mentorja in somentorja sestavljali še red. prof. dr. Aleksander Vesel, izr. prof. dr. Maria Luz Puertas in red. prof. dr. Riste Škrekovski.
Doktorska disertacija obravnava pred kratkim vpeljano Hausdorffovo razdaljo med grafi in dve novi grafovski invarianti – povezavno metrično dimenzijo grafa in mešano metrično dimenzijo grafa.
Hausdorffova razdalja med grafi je relativno nova mera podobnosti grafov. V disertaciji je obravnavana Hausdorffova razdalja med nekaterimi družinami grafov, ki se pogosto pojavljajo v kemijski teoriji grafov. Poleg rezultatov za splošne grafe so izračunane formule za Hausdorffovo razdaljo med potmi in cikli. Predstavljen je algoritem, ki reši problem določitve Hausdorffove razdalje med dvema drevesoma v polinomskem času.
Povezavna metrična dimenzija je grafovska invarianta, ki se nanaša na razlikovanje povezav grafa. V disertaciji so proučevane njene matematične lastnosti. Skozi predstavitev rezultatov o obstoju grafov z vnaprej določeno povezavno metrično dimenzijo in standardno metrično dimenzijo je narejena primerjava med obema. V disertaciji je dokazano, da je izračun povezavne metrične dimenzije povezanih grafov NP-težek problem. Poleg tega so predstavljene še meje in natančne formule za povezavno metrično dimenzijo številnih družin grafov.
Mešana metrična dimenzija grafa je grafovska invarianta, ki je podobna povezavni metrični dimenziji. Nanaša se na razlikovanje elementov grafa (vozlišč in povezav). V disertaciji je obravnavana struktura mešanih metričnih generatorjev in podana karakterizacija grafov, za katere je mešana metrična dimenzija enaka naravnim spodnjim in zgornjim mejam. Podani so tudi rezultati za mešano metrično dimenzijo nekaterih družin grafov in predstavljena je zgornja meja glede na ožino grafa. Na koncu je dokazano, da je izračun mešane metrične dimenzije povezanih grafov v splošnem NP-težek problem.
To je triinpetdeseti doktorat na Oddelku za matematiko in računalništvo.
