Magistrska naloga obravnava ožinsko-regularne in povezavno-ožinsko-regularne grafe. Podpis vozlišča u v grafu je k-terica celih števil, urejenih po velikosti od najmanjšega do največjega, kjer vsako število predstavlja število ožinskih ciklov, v katerih je vsebovana posamezna povezava, incidenčna z u. Pravimo, da je graf ožinsko-regularen (oz. tipa GR), če imajo vsa vozlišča v grafu enak podpis. Če velja, da je vsaka povezava v grafu vsebovana v enakem številu ožinskih ciklov, pravimo, da je graf povezavno-ožinsko-regularen (oz. tipa EGR). V delu predstavimo že znane rezultate o grafih tipa GR in EGR, posebej natančno pregledamo kubične grafe obeh tipov in tetravalentne grafe tipa EGR ter nekaj konstrukcij neskončnih družin takih grafov. Nato predstavimo nekaj novih rezultatov o grafih tipa EGR in klasifikacijo vseh tetravalentnih Cayleyevih grafov Abelovih grup – kaj mora veljati, da je tak graf lahko tipa EGR, ter v koliko ožinskih ciklih se potemtakem lahko nahaja vsaka povezava tega grafa.
|
