20.500.12556/RUL-111548 Girth-regular and edge-girth-regular graphs master's thesis Ožinsko-regularni in povezavno-ožinsko-regularni grafi In this work we discuss girth-regular and edge-girth-regular graphs. The signature of a vertex u in a graph is a k-tuple of integers, ordered from the smallest to the largest, where each integer represents the number of girth cycles that contain an edge, incident with u. We say that a graph is girth-regular, if every vertex has the same signature. If every edge is contained in the same number of girth cycles, the graph is edge-girth-regular. We present the known results about girth-regular and edge-girth-regular graphs, classify cubic graphs of both types up to girth 5, look at tetravalent edge-girth-regular graphs and present some constructions of infinite families of such graphs. We then present some new results on tetravalent edge-girth-regular graphs and the classification of tetravalent edge-girth-regular Cayley graphs of Abelian groups. 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. graph girth girth-regular edge-girth-regular graf ožina ožinsko-regularen povezavno-ožinsko-regularen true false false Angleški jezik Slovenski jezik Magistrsko delo/naloga 2019-10-03 07:45:22 2019-10-03 07:45:25 2024-05-30 10:19:22 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1 102632 18739289 1106.pdf 1106.pdf 1 9AD8527F2860966AFCBC0F24491C0B4A 25126433a15c1042ca4045dcf844e75cb76bfb02481c4d7100200d48217f8bec 6aa9c452-a1b7-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=123421 Fakulteta za matematiko in fiziko 0 0 0