| Abstract | 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). |
| Abstract (english) | 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). |
