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

Abstract

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.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
Publisher: [L. Lužnic]
UDC: 519.17(043.2)
COBISS: 24866824 Link will open in a new window
Views: 530
Downloads: 57
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: ǂThe ǂannihilation number of a graph and its relation with the total domination number
Secondary abstract: 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.
Secondary keywords: master theses;annihilation number;total domination number;independence number;tree;cactus graph;block graph;
Type (COBISS): Master's thesis/paper
Thesis comment: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages: IX, 63 f.
ID: 11215939