| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document Help

Title:Super dominantno število grafa
Authors:ID Remic, Tajda (Author)
ID Dravec, Tanja (Mentor) More about this mentor... New window
Files:.pdf EMAG_Remic_Tajda_2024.pdf (6,92 MB)
MD5: 911D6E7C90AA22AAEDB6CA6FA93810C4
 
Language:Slovenian
Work type:Master's thesis/paper
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract: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.
Keywords:super dominantno število, super dominantna množica, drevo, neodvisnostno število, dominantno število, prirejanje
Place of publishing:Maribor
Publisher:[T. Remic]
Year of publishing:2024
PID:20.500.12556/DKUM-88783 New window
UDC:519.17(043.2)
COBISS.SI-ID:198335747 New window
Publication date in DKUM:11.06.2024
Views:153
Downloads:34
Metadata:XML DC-XML DC-RDF
Categories:FNM
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:24.05.2024

Secondary language

Language:English
Title:Super domination number of a graph
Abstract: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.
Keywords:super domination number, super dominating set, tree, independence number, matching


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica