Na Oddelku za matematiko in računalništvo je doktorirala Polona Pavlič.

Naslov doktorske disertacije je Algebra poti in dominantni problemi na grafovskih produktih. Opravljena je bila pod mentorstvom red. prof. ddr. Janeza Žerovnika, komisijo ob zagovoru pa sta poleg mentorja sestavljala še red. prof. dr. Sandi Klavžar in doc. dr. Martin Milanič.

V doktorski disertaciji je posplošen že pred tem znan algoritem za reševanje problemov različnih grafovskih invariant na družini poligrafov (fasciagrafov in rotagrafov). Dokazano je, da lahko za veliko skupino problemov dominacije (*-dominacije) algoritem izvedemo v času, ki je pri fiksnem monografu neodvisen od števila le-teh. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, je za kartezični in direktni produkt implementiran algoritem in dobljene formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Ugotovljena je tudi zveza med *-dominantnim številom fasciagrafa in rotagrafa z istim monografom.

V drugem delu je preučevano rimsko dominantno število na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominantnih parov je za poljubna grafa podana formula, ki določi rimsko dominantno število njunega leksikografskega produkta. Podane so tudi nove neskončne družine rimskih grafov.

To je enaintrideseti doktorat na Oddelku za matematiko in računalništvo.

Accessibility