prikaz prve stranice dokumenta Mooreovi grafovi
  Download
PDF 1.51 MB
master's thesis
Mooreovi grafovi
2017. urn:nbn:hr:126:839219
Komesarović, David
Josip Juraj Strossmayer University of Osijek
Department of Mathematics
Chair of Applied Mathematics and Computer Science
Computer Science and Machine Learning Research Group

Cite this document

Komesarović, D. (2017). Mooreovi grafovi (Master's thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics. Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:839219

Komesarović, David. "Mooreovi grafovi." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:839219

Komesarović, David. "Mooreovi grafovi." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2017. https://urn.nsk.hr/urn:nbn:hr:126:839219

Komesarović, D. (2017). 'Mooreovi grafovi', Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 02 April 2025, https://urn.nsk.hr/urn:nbn:hr:126:839219

Komesarović D. Mooreovi grafovi [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2017 [cited 2025 April 02] Available at: https://urn.nsk.hr/urn:nbn:hr:126:839219

D. Komesarović, "Mooreovi grafovi", Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:126:839219

Please login to the repository to save this object to your list.
Metadata
TitleMooreovi grafovi
Title (english)Moore Graphs
AuthorDavid Komesarović
MentorSnježana Majstorović (mentor)
Committee memberKristian Sabo (predsjednik povjerenstva)
Committee memberSnježana Majstorović (član povjerenstva)
Committee memberDomagoj Ševerdija (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
(Chair of Applied Mathematics and Computer Science)
(Computer Science and Machine Learning Research Group)
Osijek
Defense date and country2017-07-07, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
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... More 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). Less
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... More 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). Less
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:839219
Study programmeTitle: Mathematics and Computer Science
Study programme type: university
Study level: integrated undergraduate and graduate
Academic / professional title: magistar/magistra edukacije matematike i informatike (magistar/magistra edukacije matematike i informatike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2017-11-09 12:48:49
accessibility

closeAccessibilityrefresh

If you wish to permanently save changes, click on Save, if not - your settings will be reset when you restart the browser.