Največja večkratnost lastnih vrednosti grafa in njegove prisilne ničle : delo diplomskega seminarja

Dolenc, Peter (avtor), Oblak, Polona (mentor)

V delu enostavnim grafom na končni množici vozlišč priredimo množico simetričnih realnih matrik, ki imajo neničeln element na mestu $(i,j)$ natanko tedaj, ko $i \ne j$ in v grafu $G$ obstaja povezava med vozliščema $i$ in $j$. Največjo večkratnost lastnih vrednosti grafa definiramo kot največjo možno večkratnost lastnih vrednosti iz pripadajoče množice matrik. Ta parameter označimo z $M(G)$. V delu definiramo tudi parameter $Z(G)$ iz grafa $G$ in pokažemo, da za vsak enostaven graf $G$ velja $M(G) \leq Z(G)$. Podrobneje študiramo grafe s prereznimi vozlišči in si ogledamo obnašanje parametrov $M(G)$ in $Z(G)$ za takšne grafe.

• Jezik: Slovenski jezik
• Ključne besede: simetrične matrike, večkratnost lastne vrednosti, prisilne ničle grafa, širitev ranga, ničelna širitev, induciran podgraf, prerezno vozlišče
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2018
• PID: 20.500.12556/RUL-103659
• UDK: 519.17
• COBISS.SI-ID: 18478937
• Datum objave v RUL: 21.09.2018

DOLENC, Peter, 2018, Največja večkratnost lastnih vrednosti grafa in njegove prisilne ničle : delo diplomskega seminarja [na spletu]. Diplomsko delo. [Dostopano 4 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=103659

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Maximum multiplicity of eigenvalues of a graph and it's zero forcing sets

Izvleček

For any simple graph with finite set of verticies we assign a set of real symmetric matrices, whose $(i,j)$th entry is non-zero whenever $i \ne j$ and $\{i,j\}$ is an edge in $G$. We define maximum multiplicity of eigenvalues of a graph to be the largest possible multiplicity of eigenvalues of matrices in that set. We denote this parameter by $M(G)$. We also define parameter $Z(G)$ and show that for any simple graph $G$, $M(G)\leq Z(G)$. We take a closer look at graphs with cut-vertices and study parameters $M(G)$ and $Z(G)$ for these graphs.

• Ključne besede: symmetric matrices, multiplicity of an eigenvalue, zero forcing set, rank spread, zero spread, induced subgraph, cut-vertex