Na Oddelku za matematiko in računalništvo je doktorirala mag. Tjaša Paj Erker.

Naslov doktorske disertacije je Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov. Opravljena je bila pod mentorstvom izr. prof. dr. Simona Špacapana, komisijo pa sta poleg mentorja sestavljala še red. prof. dr. Boštjan Brešar in zaslužni profesor za predmetno področje matematika dr. Wilfried Imrich.

Doktorska disertacija obravnava nekatere rezultate na produktih grafov.

Obravnavana je velikost in struktura največjih neodvisnih množic v direktnem produktu. Dokazano je, da ima direkten produkt lihe poti in poljubnega grafa, ter direkten produkt sodega cikla in poljubnega grafa največjo neodvisno množico, ki je unija dveh pravokotnikov. Prav tako je dokazano, da obstajajo v direktnem produktu sode poti in poljubnega grafa največje neodvisne množice, ki so lahko tudi drugačne oblike, ter zapisana natančna karakterizacija teh največjih neodvisnih množic.

Poleg tega je obravnavana posplošena 3-povezanost v kartezičnem produktu grafov. Prikazanih je več naravnih načinov, kako dobiti 3-presečno množico, pri kateri nam kartezični produkt grafov razpade na vsaj tri komponente. Dokazana je natančna vrednost posplošene 3-povezanosti kartezičnega produkta dveh 2-povezanih grafov na vsaj šestih vozliščih.

Zadnji del disertacije je posvečen zgornji meji najmanjšega diametra krepko orientiranega krepkega produkta dveh grafov. Določena je natančna vrednost najmanjšega diametra krepkega produkta dveh poti.

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

Accessibility