magistrsko delo
Lara Lužnic (Avtor), Marko Jakovac (Mentor)

Povzetek

Anihilacijsko število grafa je največje naravno število k, za katerega velja, da vsota prvih k členov v ne padajoč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 ne odvisnostnim številom grafa. Velja, da lahko ne odvisnostno š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

magistrska dela;anihilacijsko število;celotno dominantno število;neodvisnostno število;drevo;kaktus graf;bločni graf;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [L. Lužnic]
UDK: 519.17(043.2)
COBISS: 24866824 Povezava se bo odprla v novem oknu
Št. ogledov: 530
Št. prenosov: 57
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: ǂThe ǂannihilation number of a graph and its relation with the total domination number
Sekundarni povzetek: 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.
Sekundarne ključne besede: master theses;annihilation number;total domination number;independence number;tree;cactus graph;block graph;
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: IX, 63 f.
ID: 11215939