20.500.12556/DKUM-73378 Contributions to the Study of Contemporary Domination Invariants of Graphs Prispevki k preučevanju sodobnih dominacijskih invariant grafov This doctoral dissertation is devoted to contemporary domination concepts, such as the Grundy domination, the convex domination, the isometric domination and the total domination. Our main focus is to study their structure and algorithmic properties. Four Grundy domination invariants are presented, namely the Grundy domination number, the Grundy total domination number, the Z-Grundy domination number, and the L-Grundy domination number. Some bounds and properties of Grundy domination invariants are proven. All four Grundy domination parameters are studied on trees, bipartite distance-hereditary graphs, split graphs, interval graphs, Sierpi\'nski graphs, Kneser graphs and $P_4$-tidy graphs. Graphs with equal total domination number and Grundy total domination number are investigated. Convex domination and isometric domination are studied on (weak) dominating pair graphs. For the chordal dominating pair graphs we present a polynomial algorithm to compute the convex domination number, and prove the NP-completeness of the corresponding decision problem for the chordal weak dominating pair graphs. For the isometric domination number of weak dominating pair graphs an efficient algorithm is presented. Total domination is studied on the Cartesian product of graphs. We dedicate ourselves to graphs for which the equality holds in Ho's theorem, which states that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers. V doktorski disertaciji raziskujemo sodobne dominacijske koncepte, kot so Grundyjeva dominacija, konveksna dominacija, izometrična dominacija in celotna dominacija. Posvetimo se predvsem strukturnim in algoritmičnim lastnostim. Predstavljene so štiri Grundyjeve dominantne invariante, in sicer Grundyjevo dominantno število, celotno Grundyjevo dominantno število, Z-Grundyjevo dominantno število in L-Grundyjevo dominantno število. Dokazane so nekatere meje in lastnosti Grundyjevih dominantnih invariant. Vse štiri Grundyjeve dominantne parametre obravnavamo na drevesih, dvodelnih razdaljno hereditarnih grafih, razcepljenih grafih, grafih intervalov, grafih Sierpi\'nskega, Kneserjevih grafih in $P_4$-urejenih grafih. Preučujemo tudi grafe z enakim celotnim dominantnim številom in celotnim Grundyjevim dominantnim številom. Konveksna dominacija in izometrična dominacija sta raziskovani na (šibkih) grafih dominantnega para. Za tetivne grafe dominantnega para predstavimo polinomski algoritem za izračun konveksnega dominantnega števila, in dokažemo NP-polnost problema konveksnega dominantnega števila za tetivne šibke grafe dominantnega para. Za šibke grafe dominantnega para vpeljemo učinkovit algoritem za izračun izometričnega dominantnega števila. Celotno dominacijo raziskujemo na kartezičnem produktu grafov. Predvsem se posvetimo grafom za katere velja enakost v Hojevem izreku, ki pravi, da je celotno dominantno število kartezičnega produkta poljubnih dveh grafov brez izoliranih vozlišč večje ali enako polovici produkta njunih celotnih dominantnih števil. Grundy domination Grundy total domination Z-Grundy domination L-Grundy domination convex domination isometric domination total domination trees split graphs interval graphs Sierpi\'nski graphs Kneser graphs modular decomposition dominating pair graphs Cartesian product Grundyjeva dominacija celotna Grundyjeva dominacija Z-Grundyjeva dominacija L-Grundyjeva dominacija konveksna dominacija izometrična dominacija celotna dominacija drevesa razcepni grafi grafi intervalov grafi Sierpi\'nskega Kneserjevi grafi modularna dekompozicija grafi dominantnega para kartezični produkt true true false T. Kos] Angleški jezik Slovenski jezik Doktorsko delo/naloga 2019-04-02 17:20:58 2019-10-23 13:35:22 2022-08-02 00:39:41 2019-11-06 03:14:43 2019 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 2022-11-05 519.17(043.3) 302222080 URN:SI:UM:DK:W7R53FG8 DOK_Kos_Tim_2019.pdf DOK_Kos_Tim_2019.pdf 1 2B0A1F010096A2C1B1B2383B026A1C46 ae6dab25f890505dd6cbe24bfb93a760e613c12e4d5a8d81fe4a594e7afaf78b 7bf9aebf-7c07-11eb-bb7a-00155d0001ca 20.500.12556/dkum/be3e1430-4ab2-45c4-a065-2533abde3ad3 https://dk.um.si/Dokument.php?lang=slv&id=137895 DOK_Kos_Tim_2019.zip DOK_Kos_Tim_2019.zip 1 F27540FF7A8090988F77413EED7FB6CC bb3a603f8b4d93283822e7a0a947d2bb0008be861dad885d9e61bfdc337c639f f73ce4da-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/90b8ad16-29fd-4b7d-a2d6-9c482c30d7ad https://dk.um.si/Dokument.php?lang=slv&id=137896 Fakulteta za naravoslovje in matematiko 0 0 0