Na Oddelku za matematiko in računalništvo je doktoriral Matjaž Kovše. Naslov doktorske disertacije je Delne kocke in njihovi izpeljani grafi. Doktorska disertacija je napisana v angleškem jeziku (njen naslov je Partial cubes and their derived graphs). Opravljena je bila pod mentorstvom prof. dr. Sandija Klavžarja, komisijo ob zagovoru pa sta poleg mentorja sestavljala še doc. dr. Iztok Peterin in prof. dr. Wilfried Imrich.
 
V disertaciji so obravnavani različni problemi na izometričnih podgrafih hiperkock – delnih kockah. Obravnavani so štiri različni izpeljani grafi in povezave med njimi. Pokazano je, da inducirani cikel v križnem grafu medianskega grafa pomeni, da originalni graf vsebuje neko inducirano dvodelno kolo. Dokazano je, da za vsak graf G obstaja medianski graf M, tako da je G enak tau-grafu grafa M, da je tau-graf grafa G povezan natanko tedaj, ko je G pragraf glede na kartezični produkt grafov in da za poljuben medianski graf G velja, da je njegov tau-graf brez polnega podgrafa na n vozliščih natanko tedaj, ko G ne vsebuje nobene konveksne zvezde z n listi. Karakterizirani so theta-grafi, ki so 2-povezani, drevesa ali polni grafi. Podana je primerjava križnih grafov, tau-grafov in theta-grafov.
 
S pomočjo tesne povezave med križnimi grafi in grafi semikock je pokazano, da se da, v nekoliko poenostavljenem pomenu, vsak graf realizirati kot graf semikock neke delne kocke. Uvedene so terminalne semikocke in terminalne ekspanzije, ki posplošujejo periferne podgrafe in periferne ekspanzije medianskih grafov. Podrobno so obravnavani grafi semikock dreves.
 
Obravnavani in med seboj primerjani so trije različni tipi dimenzij delnih kock: izometrična, mrežna in drevesna dimenzija. Podanih je več karakterizacij delnih kock z enakimi vsemi tremi dimenzijami. Mrežna dimenzija benzenoidnih sistemov je opisana s pomočjo izometričnih vložitev benzenoidnih sistemov v kartezični produkt treh dreves.
 
Obravnavano je vprašanje Fukude in Hande o tem, ali je vsaka uravnotežena delna kocka G tudi harmonično-uravnotežena. Pokazano je, da je odgovor na vprašanje pozitiven, če je izometrična dimenzija G enaka diametru G, kar drži za delne kocke izometrične dimenzije kvečjemu 6. Pokazano je tudi, da pod dodatnimi posebnimi pogoji velja, da je vsaka uravnotežena delna kocka bodisi tudi harmonično-uravnotežena, bodisi za dve sosedni vozlišči velja, da sta njuni diametralni vozlišči na razdalji vsaj 4. Dokazano je tudi, da so uravnotežene delne kocke globine 1.
 
To je dvajseti doktorat na oddelku za matematiko in računalništvo.
Accessibility