magistrsko delo
Tilen Lučovnik (Author), Polona Oblak (Mentor)

Abstract

Enostavnemu grafu $G$ z $n$ vozlišči definiramo matriko sosednosti in Laplaceovo matriko. Obe imata realne lastne vrednosti. Lastne vrednosti matrike sosednosti označimo s $\theta_1(G) \geq \cdots \geq \theta_n(G)$, lastne vrednosti Laplaceove matrike pa z $\lambda_1(G) \geq \cdots \geq \lambda_n(G) = 0$. V delu študiramo neenakosti Nordhaus-Gaddumovega tipa za lastne vrednosti matrike sosednosti in Laplaceove matrike. To so omejitve na vsote oblik $\theta_i(G) + \theta_i(\overline{G})$ in $\lambda_j(G) + \lambda_j(\overline{G})$ za določene vrednosti indeksov $i$ in $j$, pri čemer je $\overline{G}$ komplement grafa $G$. Posebej se osredotočimo na preučevanje vsot za najmanjšo lastno vrednost matrike sosednosti in največji dve lastni vrednosti Laplaceove matrike.

Keywords

matematika;neenakosti Nordhaus-Gaddumovega tipa;matrika sosednosti;Laplaceova matrika;lastne vrednosti;algebraična povezanost;

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [T. Lučovnik]
UDC: 519.1
COBISS: 66285571 Link will open in a new window
Views: 848
Downloads: 62
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Nordhaus-Gaddum type inequalities for Laplacian eigenvalues
Secondary abstract: For a simple graph $G$ of order $n$, we define its adjacency matrix and Laplacian matrix. Both have real eigenvalues. Let $\theta_1(G) \geq \cdots \geq \theta_n(G)$ be the eigenvalues of the adjacency matrix and $\lambda_1(G) \geq \cdots \geq \lambda_n(G) = 0$ the eigenvalues of the Laplacian matrix of graph $G$. We study Nordhaus-Gaddum type inequalities for the eigenvalues of these two matrices. These are upper and lower bounds for sums of the forms $\theta_i(G) + \theta_i(\overline{G})$ and $\lambda_j(G) + \lambda_j(\overline{G})$, where $\overline{G}$ denotes the graph complement of $G$. The focus of this work is on the sums for the smallest eigenvalue of the adjacency matrix and the largest two eigenvalues of the Laplacian matrix.
Secondary keywords: mathematics;Nordhaus-Gaddum type inequalities;adjacency matrix;Laplacian matrix;eigenvalues;algebraic connectivity;
Type (COBISS): Master's thesis/paper
Study programme: 0
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 2. stopnja
Pages: IX, 70 str.
ID: 13011137