20.500.12556/RUL-186767 Mooreovi grafi in posplošeni večkotniki delo diplomskega seminarja Moore graphs and generalized polygons V diplomskem delu preučujemo Mooreove grafe, ki pri dani maksimalni stopnji in premeru dosegajo teoretično zgornjo mejo za število vozlišč. Analiziramo njihove strukturne lastnosti, ki nam kasneje služijo pri analizi njihovega obstoja. Eksplicitno konstruiramo trivialne Mooreove grafe, nakar dokažemo enoličnost Hoffman-Singletonovega grafa, ki je skupaj s Petersenovim grafom, eden od dveh znanih netrivialnih Mooreovih grafov. Navedemo podrobno klasifikacijo vseh Mooreovih grafov, pri čemer v edinem nezajetem primeru, Aschbacherjevem grafu valence 57, pokažemo, da ta, če obstaja, ni razdaljno tranzitiven. V nadaljevanju obrnemo perspektivo in utemeljimo, da Mooreova meja predstavlja tudi spodnjo mejo za število vozlišč pri grafih z vnaprej določeno stopnjo in ožino. Izostritev te meje nato usmeri pozornost na dvodelne Mooreove grafe, ki naravno sovpadajo z regularnimi posplošenimi večkotniki. Analiziramo njihove konstrukcije, pri čemer se srečamo s projektivnimi ravninami, ortogonalnimi, simplektičnimi in Titsovimi posplošenimi štirikotniki ter klasičnimi posplošenimi šestkotniki. Z znanimi konstrukcijami in klasifikacijo regularnih posplošenih večkotnikov zaključimo nalogo, pri kateri smo od togega ekstremalnega problema v teoriji grafov prešli v bogato geometrijo ranga 2. In this thesis, we study Moore graphs, which attain the theoretical upper bound for the number of vertices given a specific maximal degree and diameter. We analyze their structural properties, which later serve as a basis for studying their existence. We explicitly construct the trivial Moore graphs and prove the uniqueness of the Hoffman-Singleton graph, which, together with the Petersen graph, is one of the two known nontrivial Moore graphs. We provide a detailed classification of all Moore graphs and, in the only remaining case, the Aschbacher graph of valency 57, show that if it exists, it is not distance-transitive. We then shift our perspective and show that the Moore bound also provides a lower bound for the number of vertices in graphs with prescribed degree and girth. Sharpening this bound leads to the study of bipartite Moore graphs, which naturally correspond to regular generalized polygons. We analyze their constructions, encountering projective planes, orthogonal, symplectic, and Tits generalized quadrangles, as well as classical generalized hexagons. We conclude with a classification of the known regular generalized polygons, thereby tracing a path from a rigid extremal problem in graph theory to the rich geometry of rank 2. Mooreovi grafi Mooreova meja problem stopnje in premera Hoffman-Singletonov graf posplošeni večkotniki geometrija ranga 2 Moore graphs Moore bound degree-diameter problem Hoffman-Singleton graph generalized polygons rank 2 geometry true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2026-09-05 08:15:07 2026-09-05 08:15:20 2026-09-07 10:43:34 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.17 162679 290140931 23921.pdf 23921.pdf 1 1C5507C5A337E8DB17960B24D474FA6A 2d3b6e4494add0a617207e516b78349cb2931aa7c6e451be6f4fb2098f9e9532 2abfecb0-a8f1-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=246138 Fakulteta za matematiko in fiziko 0 0 0