Lastnosti Laplaceovih matrik enostavnih in mešanih grafov : magistrsko delo

Marolt, Saša (author), Oblak, Polona (mentor)

V magistrski nalogi obravnavamo spektralno teorijo enostavnih in mešanih grafov. Za Laplaceove matrike enostavnih grafov pokažemo, da je večkratnost lastne vrednosti nič enaka številu povezanih komponent grafa in preučimo celoštevilske lastne vrednosti Laplaceovih matrik dreves. Za mešane grafe pokažemo, da imajo Laplaceove matrike kvazidvodelnih grafov enak spekter kot Laplaceove matrike pripadajočih temeljnih enostavnih grafov. Predstavimo klasifikacijo vseh nesingularnih povezanih mešanih grafov na vsaj sedmih vozliščih, katerih Laplaceova matrika ima natanko dve lastni vrednosti večji od dve.

• Language: Slovenian
• Keywords: Laplaceova matrika, enostavni grafi, mešani grafi
• Work type: Master's thesis/paper
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2021
• PID: 20.500.12556/RUL-128155
• UDC: 519.1
• COBISS.SI-ID: 69014019
• Publication date in RUL: 04.07.2021

Secondary language

• Language: English
• Title: Properties of Laplacian matrices of simple and mixed graphs

Abstract

In this work we discuss the spectral theory of simple and mixed graphs. For the Laplacian matrix of a simple graph we show that the multiplicity of the eigenvalue zero equals the number of connected components of the graph and we examine integer eigenvalues of the Laplacian matrix of a tree. For a mixed graph we show that the Laplacian matrix of a quasi-bipartite graph has the same spectrum as the Laplacian matrix of the corresponding underlying simple graph. We present the classification of all nonsingular connected mixed graphs on at least seven vertices whose Laplacian matrices have exactly two eigenvalues greater than two.

• Keywords: Laplacian matrix, simple graphs, mixed graphs