20.500.12556/RUL-186226 Karakterizacije in konstrukcije $r$-grafov razreda II magistrsko delo Characterizations and constructions of class II r-graphs V 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. In this thesis, we study $r$-graphs, that is, $r$-regular graphs in which the edge boundary of every vertex set of odd cardinality contains at least $r$ edges. A special role among them is played by $r$-graphs of class II, which form a natural generalization of snarks to graphs of higher regularity. Due to their close connections with perfect matchings, edge colouring, and several important open conjectures in graph theory, $r$-graphs represent one of the central structures in this area. We present their characterizations, properties, and constructions, as well as their role in the study of class II graphs. Particular emphasis is placed on two new constructions. The first constructs, from an arbitrary $r$-graph, an $(r+1)$-graph preserving the odd-boundary condition; the resulting graph is always of class I. The second is based on the chaining of dipoles and preserves regularity, the odd-boundary condition, and the graph’s membership in the corresponding chromatic-index class. These constructions yield new families of $r$-graphs and broaden the range of constructive approaches available for their study. $r$-grafi barvanje povezav kromatični indeks popolna prirejanja snarki politop popolnih prirejanj konstrukcije grafov grafi razreda II $r$-graphs edge colouring chromatic index perfect matchings snarks perfect matching polytope graph constructions class II graphs true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2026-08-28 13:17:28 2026-08-28 13:17:44 2026-09-25 10:17:30 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1 162018 291046147 23723.pdf 23723.pdf 1 DF93309ACB1B89F45C69AE21465EFAA6 9c8f29c61c5509090d7d896bdca7eeb34708082a28d3795dd61e5f84dc53c3ac ae490317-a2d1-11f1-9b0d-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=245347 Fakulteta za matematiko in fiziko 0 0 0