20.500.12556/DKUM-88783 Super dominantno število grafa Super domination number of a graph Množica $D$ vozlišč grafa $G$ je super dominantna množica, če za vsako vozlišče $v \in V(G)-D$ obstaja vozlišče $u \in D$, ki je sosednje z $v$ in velja, da je $v$ edini sosed od $u$ v $V(G)-D$. Velikost najmanjše super dominantne množice grafa $G$ je super dominantno število grafa $G$, ki ga označujemo z $\gamma_{sp}(G)$. V magistrskem delu raziskujemo lastnosti super dominantnega števila. V ta namen najprej predstavimo osnovne pojme na grafih, predstavimo nekaj pomembnih družin grafov in veliko različnih grafovskih invariant, ki so povezane s super dominantnim številom. V drugem delu pričnemo z raziskovanjem super dominantnih množic. Najprej izračunamo super dominantno število za nekaj pomembnih družin grafov in dokažemo, da za vsak povezan graf na vsaj dveh vozliščih velja: $\frac{n}{2} \leq \gamma_{sp}(G)\leq |V(G)|-1$. Nato super dominantno število raziskujemo na drevesih. Dokažemo boljšo zgornjo mejo super dominantnega števila dreves in se ukvarjamo z grafi, ki to mejo dosežejo. Na koncu super dominantno število dreves navzgor omejimo še z $2$-dominantnim številom grafa. V zadnjem delu magistrske naloge predstavimo zvezo super dominantnega števila z mnogimi grafovskimi invariantami, kot so velikost največjega prirejanja, neodvisnostno število in mnoge druge. A set $D$ of vertices of a graph $G$ is a super dominating set if for every vertex $v$ of $V(G)-D$ there exists a vertex $u$ of $D$ which is adjacent to $v$ and $v$ is the only neighbour of $u$ in $V(G)-D$. The size of the smallest super dominating set of a graph $G$ is the super domination number of the graph $G$, which is denoted by $\gamma_{sp}(G)$. In this thesis we investigate the properties of the super domination number. We first introduce basic notions on graphs, present some important families of graphs and many different graph invariants related to the super dominanion number. In the second part, we start by exploring super dominating sets. First, we compute the super domination number for some important graph families and prove that for every connected graph on at least two vertices, $\frac{n}{2} \leq \gamma_{sp}(G)\leq |V(G)|-1$ holds. We then investigate the super domination number on trees. We prove a better upper bound on the super domination number of trees and work on graphs that reach this bound. Finally, we present an upper bound for the super domination number of trees with respect to the $2$-domination number. In the last part of the thesis we present the relation of the super domination number of a graph $G$ with many graph invariants, such as the matching number of $G$, the independence number of $G$ and many others. super dominantno število super dominantna množica drevo neodvisnostno število dominantno število prirejanje super domination number super dominating set tree independence number matching true true false [T. Remic] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2024-05-24 06:15:13 2024-06-11 09:52:50 2024-06-12 03:12:26 0000-00-00 00:00:00 2024 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 198335747 EMAG_Remic_Tajda_2024.pdf EMAG_Remic_Tajda_2024.pdf 1 911D6E7C90AA22AAEDB6CA6FA93810C4 30236434804224678aca62c92bfee497f29786c3cd3fc9af6a06718427ef8ed2 f9b7d4fe-198a-11ef-a532-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=179709 Fakulteta za naravoslovje in matematiko 0 0 0