| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Anihilacijsko število grafa in njegova povezava s celotnim dominantnim številom
Avtorji:Lužnic, Lara (Avtor)
Jakovac, Marko (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf MAG_Luznic_Lara_2019.pdf (730,62 KB)
MD5: FF2638FAB0164AE002357563303DE5A6
 
Jezik:Slovenski jezik
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Tipologija:2.09 - Magistrsko delo
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis:Anihilacijsko število grafa je največje naravno število k, za katerega velja, da vsota prvih k členov v nepadajočem zaporedju stopenj grafa ne presega števila povezav tega grafa. V magistrskem delu je predstavljena definicija anihilacijskega števila, nekatere njegove lastnosti ter njegova povezava s celotnim dominantnim številom grafa. V prvem poglavju so predstavljeni osnovni pojmi in rezultati iz teorije grafov, ki jih potrebujemo za definiranje pojmov in dokazovanje v nadaljevanju. V drugem poglavju je na podlagi anihilacijskega procesa izpeljana definicija anihilacijska števila, opisana je povezava med anihilacijskim procesom in Havel-Hakimijevim algoritmom, predstavljene so nekatere lastnosti anihilacijskega števila in algoritem za iskanje le-tega. V tem delu je izpostavljena tudi povezava med anihilacijskim in neodvisnostnim številom grafa. Velja, da lahko neodvisnostno število navzgor omejimo z anihilacijskim številom. Ta meja je v nekaterih primerih natančnejša od drugih znanih mej. V zadnjem poglavju je podrobneje obravnavana povezava med anihilacijskim in celotnim dominantnim številom. Postavljena je domneva, da lahko v vsakem netrivialnem grafu celotno dominantno število navzgor omejimo z anihilacijskim številom. V magistrskem delu bo ta domneva dokazana za grafe z najmanjšo stopnjo 3, cikle, drevesa, kaktus grafe in bločne grafe.
Ključne besede:anihilacijsko število, celotno dominantno število, neodvisnostno število, drevo, kaktus graf, bločni graf
Leto izida:2019
Založnik:[L. Lužnic]
Izvor:Maribor
UDK:519.17(043.2)
COBISS_ID:24866824 Novo okno
NUK URN:URN:SI:UM:DK:OTTREDWM
Število ogledov:309
Število prenosov:30
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:05.09.2019

Sekundarni jezik

Jezik:Angleški jezik
Naslov:The annihilation number of a graph and its relation with the total domination number
Opis:The annihilation number of a graph is the maximum positive integer k, such that the sum of the first k terms in a non-decreasing degree sequence is less or equal to the number of edges of this graph. In this master thesis we introduce the definition of the annihilation number, some of its properties and its relation with total domination number. In the first chapter we introduce some of the basic definitions and results from graph theory, which are needed for definitions and proofs in later chapters. In the second chapter we describe the annihilation process, from which we form the definition of the annihilation number. The relation between Havel-Hakimi algorithm and some of the properties of the annihilation number are introduced, and we describe the algorithm for determination of the annihilation number. In this part we also introduce the relation between the annihilation and the independence number. It is shown that the annihilation number is a sharp upper bound for independence number. In some cases this bound is a better approximation than some other bounds. In the last chapter we describe the relation between the annihilation and the total domination number. It is conjectured that the annihilation number is an upper bound for the total domination number for every nontrivial graph. In this master thesis we prove the conjecture for graphs with minimum degree 3, cycles, trees, cactus graphs and block graphs.
Ključne besede:annihilation number, total domination number, independence number, tree, cactus graph, block graph


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici