Jako regularni grafovi

master's thesis

• Author: Luka Crnoja
• Mentor: Vedran Krčadinac (mentor)
• Committee member: Vedran Krčadinac (predsjednik povjerenstva)
• Committee member: Ozren Perše (član povjerenstva)
• Committee member: Boris Širola (član povjerenstva)
• Committee member: Maja Resman (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Tema ovog diplomskog rada su jako regularni grafovi. Diplomski rad je podijeljen u četiri poglavlja i dodatak. U prvom poglavlju cilj je upoznati se s definicijom jako regularnog grafa i osnovnim uvjetima koji vrijede za svaki jako regularan graf. Dani su primjeri nekih jako regularnih grafova i njihovi parametri. Slike grafova prate sadržaj prvog poglavlja. U drugom poglavlju proučavamo spektar jako regularnih grafova. Nalazimo formulu za kratnosti njegovih svojstvenih vrijednosti, koje moraju biti nenegativni cijeli brojevi. Ovaj rezultat se naziva uvjet cjelobrojnosti i daje nam snažan kriterij za nepostojanje jako regularnog grafa. U trećem poglavlju otkrivamo dva sljedeća kriterija za egzistenciju jako regularnih grafova: apsolutnu među i Kreinove uvjete. U četvrtom poglavlju koristimo sve prethodno dobivene rezultate o jako regularnim grafovima. Cilj je napraviti tablicu dopustivih parametara \((v,k,\lambda,\mu)\) koji zadovoljavaju nužne uvjete iz prvog poglavlja i uvjet cjelobrojnosti. Uspoređujemo našu tablicu s Brouwerovom tablicom jako regularnih grafova i nalazimo da ona sadrži točno iste parametre za \(v \leq 50\). Također su dane informacije o egzistenciji i broju jako regularnih grafova. Dodatak sadrži kod napisan u programskom paketu Maxima koji smo koristili za izradu tablice dopustivih parametara jako regularnih grafova.

Abstract (english)

The topic of this thesis are strongly regular graphs. The thesis is divided into four sections and an appendix. In the first section, the goal is to get acquainted with the definition of a strongly regular graph and the basic conditions that apply. We give examples of some strongly regular graphs and their parameters. Pictures of the graphs accompany the contents of the first section. In the second section we study the spectrum of strongly regular graphs. We find formulae for the multiplicity of their eigenvalues, which must be integers. This result is referred to as the integrality condition, and provides a powerful non-existence criterion for strongly regular graphs. In the third section two further existence criteria for strongly regular graphs are presented: the absolute bound and the Krein conditions. In the fourth section all of the previous results about strongly regular graphs are put to use. The goal is to make a table of admissible parameters \((v,k,\lambda,\mu)\) satisfying the necessary conditions from the first section and the integrality condition. We compare our table with A. E. Brouwer’s table of strongly regular graphs, and find that it contains exactly the same parameters for \(v \leq 50\). Information about the existence and the number of strongly regular graphs is also given. The appendix contains code in the computer algebra system Maxima we used to make the table of admissible parameters of strongly regular graphs.

• Keywords: jako regularni grafovi; uvjet cjelobrojnosti; apsolutna međa; Kreinovi uvjeti; Brouwerova tablica; Maxima
• Keywords (english): strongly regular graphs; integrality condition; absolute bound; Krein conditions; Brouwer’s table; Maxima
• Language: croatian
• URN:NBN: urn:nbn:hr:217:008421
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-03-26 12:57:18