Anihilacijsko število grafa in njegova povezava s celotnim dominantnim številomLužnic, Lara (Avtor) Jakovac, Marko (Mentor) anihilacijsko številocelotno dominantno številoneodvisnostno številodrevokaktus grafbločni grafAnihilacijsko š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.[L. Lužnic]20192019-09-05 17:31:55Magistrsko delo/naloga74762sl