1111 KB0 KB0 KB2016Azarija, JernejKlavžar, SandiX, 66 str., 30 cmCOBISSID:17671513PID:https://repozitorij.uni-lj.si/IzpisGradiva.php?id=95865URN:URN:NBN:SI:doc-AQ5X8N5MenJ. Azarijavisokošolska delaadjacency matrixchromatic polynomialsconvex cycleDisertacijekonveksni cikelkrepko regularni grafikromatični polinomimatrika sosednostistrongly regular graphsTeorija grafovTutte polynomialTuttov polinomSome results from algebraic graph theory| doctoral dissertation|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 RowlinsonV 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 grafeTEXTvisokošolska delatheses and dissertationsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza v Ljubljani, Fakulteta za matematiko in fiziko