Podrobno

Some results from algebraic graph theory : doctoral dissertation
ID Azarija, Jernej (Avtor), ID Klavžar, Sandi (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (955,99 KB)
MD5: 1C8FBFD356BC51C32162B2B24B3EE297
PID: 20.500.12556/rul/88598ee3-ac8f-448c-bcfd-328bdab35308

Izvleček
In this thesis we present some results living in the intersection between graph theory and linear algebra. We introduce the subject of algebraic graph theory presenting some general results from this area. In particular we show how certain algebraic objects such as matrices and polynomials can be used to gain structural information about graphs. We then introduce two graph polynomials namely the chromatic polynomial and its generalization - the Tutte polynomial. We present a counterexample to a conjecture of J. Xu and Z. Liu about the chromatic polynomial and degree sequences. We then turn our attention to matrices associated with graphs namely the adjacency matrix and distance matrix. We present some results in the context of strongly regular graphs. In particular we show a connection between graphs maximizing the number of cycles with length matching their odd girth and Moore graphs. Continuing with strongly regular graphs we present a classificational result for strongly regular graphs. The approach is based on the so called star complement technique developed by Cvetković and Rowlinson.

Jezik:Angleški jezik
Ključne besede:adjacency matrix, strongly regular graphs, chromatic polynomials, Tutte polynomial, convex cycle
Vrsta gradiva:Doktorsko delo/naloga
Tipologija:2.08 - Doktorska disertacija
Organizacija:FMF - Fakulteta za matematiko in fiziko
Kraj izida:Ljubljana
Založnik:[J. Azarija]
Leto izida:2016
Št. strani:X, 66 str.
PID:20.500.12556/RUL-95865 Povezava se odpre v novem oknu
UDK:519.17(043.3)
COBISS.SI-ID:17671513 Povezava se odpre v novem oknu
Datum objave v RUL:24.10.2017
Število ogledov:5047
Število prenosov:457
Metapodatki:XML DC-XML DC-RDF
:
AZARIJA, Jernej, 2016, Some results from algebraic graph theory : doctoral dissertation [na spletu]. Doktorska disertacija. Ljubljana : J. Azarija. [Dostopano 20 julij 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=95865
Kopiraj citat
Objavi na:Bookmark and Share

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Nekaj rezultatov iz algebraične teorije grafov
Izvleček:
V disertaciji predstavimo nekaj rezultatov, ki ležijo na preseku med teorijo grafov in linearno algebro. Predstavimo področje algebraične teorije grafov in vpeljemo nekaj znanih rezultatov iz tega področja. Natančneje, pokažemo, kako nam lastnosti grafovskih polinomov in matrik določajo strukturne lastnosti ustreznih grafov. Konkretneje se osredotočimo na matriko sosednosti, razdaljno matriko in kromatični polinom. V kontekstu kromatičnega polinoma konstruiramo neskončno družino protiprimerov za domnevo J. Xu-ja in Z. Liu-ja. V nadaljevanju disertacije se osredotočimo na pojem krepko regularnih grafov in razvijemo nekaj njihovih osnovnih lastnosti. Med drugim pokažemo tudi ekstremalno povezavo med številom konveksnih ciklov ter poddružino krepko regularnih grafov - Moorovih grafov. Konec posvetimo problemu klasifikacije krepko regularnih grafov. S pomočjo metode zvezdnega komplementa klasificiramo krepko regularne grafe.

Ključne besede:matrika sosednosti, krepko regularni grafi, kromatični polinomi, Tuttov polinom, konveksni cikel, Teorija grafov, Disertacije

Podobna dela

Podobna dela v RUL:
  1. Using synthetic data to train convolutional neural networks for the case of hand detection
  2. Computer vision on embedded devices for natural user interfaces
  3. Long-term object tracking using region proposals
  4. Segmentacija rok za obogateno resničnost
  5. Melt pool detection at wire arc welding
Podobna dela v drugih slovenskih zbirkah:
  1. Person age estimation based on digital images using convolutional neural networks
  2. Development of an advanced system for lane detection on GPU platforms
  3. Food recognition from digital images using convolutional neural networks
  4. Time series classification based on convolutional neural networks
  5. The preparation of photos' dataset and its classification using deep neural networks

Nazaj