Some results from algebraic graph theory : doctoral dissertation

Azarija, Jernej (author), Klavžar, Sandi (mentor)

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.

• Language: English
• Keywords: adjacency matrix, strongly regular graphs, chromatic polynomials, Tutte polynomial, convex cycle
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [J. Azarija]
• Year: 2016
• Number of pages: X, 66 str.
• PID: 20.500.12556/RUL-95865
• UDC: 519.17(043.3)
• COBISS.SI-ID: 17671513
• Publication date in RUL: 24.10.2017

Secondary language

• Language: Slovenian
• Title: Nekaj rezultatov iz algebraične teorije grafov

Abstract

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.

• Keywords: matrika sosednosti, krepko regularni grafi, kromatični polinomi, Tuttov polinom, konveksni cikel, Teorija grafov, Disertacije