20.500.12556/DKUM-37206 NEENAKOSTI VIZINGOVEGA TIPA ZA RAZLIČNE DOMINACIJSKE INVARIANTE VIZING-TYPE INEQUALITIES FOR VARIOUS DOMINATION GRAPH INVARIANTS Dominacija na grafih je intenzivno raziskovana veja v teoriji grafov. Leta 1963 je Vizing postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov kvečjemu večje od produkta njunih dominantih števil. Mnogo delnih rezultatov je bilo dokazanih, vendar pa je le-ta še vedno eden izmed največjih odprtih problemov v študiju dominacije na grafih. V tem diplomskem delu so v ospredju obravnavani najbolj znani izreki Vizingovega tipa za različne dominacijske invariante. Na začetku predstavimo nekaj dejstev o dominaciji na kartezičnem produktu. Opišemo znan Clark-Suenov rezultat Vizingovega tipa in t.i. razstavljive grafe, za katere Vizingova domneva drži. Drugi del se nanaša na pet dominacijskih invariant; totalno, celoštevilsko, zgornjo, deljeno dominantno število in dominacijo po parih. Predstavljeni so izreki Vizingovega tipa za posamezne dominacijske parametre, kot na primer izrek za deljeno-dominantno število, Ho-jev izrek o totalnem dominantnem številu in izrek Vizingovega tipa za zgornje dominantno število. Domination in graphs is an extensively studied branch of graph theory. In 1963 Vizing conjectured that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers. Several partial results have been proven, but the conjecture still remains one of the biggest open problems in the study of domination in graphs. In the thesis our main focus are some of the most important variations of Vizing's conjecture for various domination-type invariants. At the beginning we explain some facts about domination in Cartesian products. We present famous Clark-Suen Vizing-type result and the so-called decomposable graphs, for which Vizing's conjecture is true. In the last part we survey versions for five main domination invariants; total, integer, upper, fractional and paired. Further on we describe Vizing-type theorems for several domination parameters, for instance theorem for fractional domination number, conjecture for total domination number solved by Ho and Vizing-type theorem for upper domination number. dominantna množica dominantno število Vizingova domneva dominacijske invariante domination set domination number Vizing's conjecture domination graph invariants true true false [V. Koban] Slovenski jezik Angleški jezik Diplomsko delo 2012-08-21 10:43:34 2012-09-11 14:26:18 2022-04-22 11:15:02 2021-04-17 03:22:02 2012 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 51(043.2) 19318024 URN:SI:UM:DK:0YUNECK2 UNI_Koban_Vika_2012.pdf UNI_Koban_Vika_2012.pdf 1 F23F2A3621E365F1B3D87609C15B51CC d5b81deda32cf28285f4d30a91148343dad7933cf1b142fac3bad04c27a9a0b2 2fa1ff3a-7c08-11eb-bb7a-00155d0001ca 20.500.12556/dkum/51212bde-0640-4b9d-94f9-b4ea1ee54a58 https://dk.um.si/Dokument.php?lang=slv&id=48884 Fakulteta za naravoslovje in matematiko 0 0 0