Moore Graphs

Mooreovi grafovi su vrlo rijetka klasa grafova s vrlo zanimljivim svojstvima. To su ekstremalni grafovi, tj. grafovi s ekstremalnim svojstvima: za zadani najveći stupanj i dijametar imaju najveći mogući broj vrhova. Mooreovih grafova je tako malo da ih možemo nabrojati ”na prste”. U ovom radu su detaljno obrađena svojstva tih grafova, a posebno je analiziran Mooreov graf tipa (3, 2) ili Petersenov graf. Njegova posebnost je u tome što se često pojavljuje kao kontraprimjer kod pokušaja dokazivanja mnogih tvrdnji. Mooreovi grafovi su regularni pa ih nije suviše teško konstruirati. Najveći Mooreov graf koji je uspješno konstruiran je Hoffman-Singleton graf ili Mooreov graf tipa (7, 2). Radi se o 7-regularnom grafu s 50 vrhova i 175 bridova. U radu su navedene neke konstrukcije tog grafa. Najveći izazov u proučavanju Mooreovih grafova je konstrukcija Mooreova grafa tipa (57, 2). Iako je graf aritmetički izvediv, nitko ga dosad nije uspio konstruirati, tj. i dalje se ne zna postoji li. Kada bi postojao, imao bi 3250 vrhova i 92625 bridova. Stoga je egzistencija Mooreovog grafa tipa (57, 2) još uvijek otvoren problem u teoriji grafova. Budući da su Mooreovi grafovi otkriveni tek 1960. godine, možemo zaključiti da je ovaj dio teorije grafova dosta ”mlad” pa postoji još dosta prostora za napredak i dokazivanje egzistencije Mooreovog grafa tipa (57, 2).Moore graphs is a very rare class of graphs with an interesting properties. These graphs are extremal, that is, they have extremal properties: for fixed maximum degree and diameter, they have the largest possible number of vertices. There are only few Moore graphs, so we can count them in a few seconds. The main part of this diploma thesis is concerned with the analysis of properties of Moore graphs, and a special attention is given to Moore graph of type (3, 2) or Petersen graph. It is a very special graph because it appears very often as a counterexample when one tries to prove some statement. Moore graphs are regular graphs, which makes their construction not to difficult. The largest Moore graph which was successfully constructed is the Hoffman – Singleton graph, that is, the Moore graph of type (7, 2). This graph is 7-regular with 50 vertices and 175 edges. The biggest challenge in the study of Moore graphs is the construction of Moore graph (57, 2). Although this graph is arithmetically feasible, nobody has proved its existance. If such graph would exist, it would have 3250 vertices and 92625 edges. So the existance of Moore graph of type (57, 2) is still an open problem in graph theory. Since Moore graph have been discovered in 1960s, we can conclude that this part of graph theory is still ”young”, so there is enough time for progress in proving the existance of Moore graph (57, 2)