20.500.12556/DKUM-83117 Grafi, ki dosežejo enakost v vizingovi domnevi magistrsko delo Graphs achieving the equality in vizing's conjecture na študijskem programu 2. stopnje Matematika Vizing je leta 1968 postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov večje ali enako produktu njunih dominantnih števil. V magistrskem delu obravnavamo družine grafov, ki v tej domnevi dosežejo enakost. V prvem delu magistrske naloge smo navedli pojme in trditve, ki jih potrebujemo za razumevanje glavnega problema naloge. Drugo poglavje se nanaša na različne meje dominantnega števila kartezičnega produkta dveh grafov in družine grafov, ki zadoščajo Vizingovi domnevi. V tretjem poglavju obravnavamo družine grafov, ki pod določenimi pogoji dosežejo enakost v Vizingovi domnevi, ter znane rezultate podamo v tabeli. In 1963, Vizing conjectured that the domination number of the Cartesian product of two graphs is greater or equal to the product of their domination numbers. In this master’s thesis, we discuss graph classes that achieve equality in this conjecture. In the first part, we list all the necessary definitions and theorems that are needed for understanding the main problem of the thesis. In the second part, we present different bounds for the domination number of the Cartesian product of two graphs and graph classes that satisfy Vizing’s conjecture. In the third part, we study graph classes that under various conditions satisfy the equality in Vizing’s conjecture and present known results in a table. dominantno število dominantna množica Vizingova domneva enakost v Vizingovi domnevi domination number domination set Vizing’s conjecture equality in Vizing’s conjecture true true false [A. Lakner] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-09-19 13:37:01 2022-10-28 11:16:53 2022-10-29 03:08:59 0000-00-00 00:00:00 2022 0 Maribor 0 Maribor VIII, 54 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 127467779 MAG_Lakner_Anamarija_2022.pdf MAG_Lakner_Anamarija_2022.pdf 1 C8346B452984403A309DF0BC42573DB3 6cd17d3a602cb396464b22ad3360e12a3ddcc866d6a1fb84dc744b71a6d9b6a8 b4777f70-3811-11ed-9353-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=162941 Fakulteta za naravoslovje in matematiko 0 0 0