doctoral dissertation
Jernej Azarija (Avtor), Sandi Klavžar (Mentor)

Povzetek

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

adjacency matrix;strongly regular graphs;chromatic polynomials;Tutte polynomial;convex cycle;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 2.08 - Doktorska disertacija
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
Založnik: [J. Azarija]
UDK: 519.17(043.3)
COBISS: 17671513 Povezava se bo odprla v novem oknu
Št. ogledov: 1343
Št. prenosov: 352
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Nekaj rezultatov iz algebraične teorije grafov
Sekundarni povzetek: 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.
Sekundarne ključne besede: matrika sosednosti;krepko regularni grafi;kromatični polinomi;Tuttov polinom;konveksni cikel;Teorija grafov;Disertacije;
Vrsta dela (COBISS): Doktorsko delo/naloga
Komentar na gradivo: Univ. Ljubljana, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Strani: X, 66 str.
ID: 10865403