Karakterizacije in konstrukcije $r$-grafov razreda IIBlažič, Nika (Avtor) Žitnik, Arjana (Mentor) $r$-grafibarvanje povezavkromatični indekspopolna prirejanjasnarkipolitop popolnih prirejanjkonstrukcije grafovgrafi razreda IIV magistrskem delu obravnavamo $r$-grafe, to je $r$-regularne grafe, pri katerih ima rob vsake množice vozlišč lihe moči vsaj $r$ povezav. Med njimi imajo posebno mesto $r$-grafi razreda II, ki so naravna posplošitev snarkov na grafe višje regularnosti. Zaradi tesne povezave s popolnimi prirejanji, barvanjem povezav in pomembnimi odprtimi domnevami teorije grafov $r$-grafi predstavljajo eno izmed osrednjih struktur na tem področju. V delu predstavimo njihove karakterizacije, lastnosti in konstrukcije ter njihovo vlogo pri proučevanju grafov razreda II. Poseben poudarek je namenjen dvema novima konstrukcijama. Prva iz poljubnega $r$-grafa konstruira $(r+1)$-graf ob ohranitvi pogoja robov množic lihe moči; dobljeni graf je vedno razreda I. Druga temelji na verižnem povezovanju dipolov in ohranja regularnost, pogoj robov množic lihe moči ter pripadnost razredu glede na kromatični indeks. S tem dobimo nove družine $r$-grafov in razširimo nabor konstrukcijskih pristopov za njihovo proučevanje.20262026-08-28 13:17:28Magistrsko delo/naloga186226sl