Some results from algebraic graph theory : doctoral dissertation

angleški

doktorska dela

2016

adjacency matrix   chromatic polynomials   convex cycle   Disertacije   konveksni cikel   krepko regularni grafi   kromatični polinomi   matrika sosednosti   strongly regular graphs   Teorija grafov   Tutte polynomial   Tuttov polinom

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

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.

12.05.2023