20.500.12556/DKUM-83575 Meje za mavrična dominantna števila magistrsko delo Bounds on rainbow domination numbers na študijskem programu enovitega magistrskega programa Izobraževalna matematika (dvopredmetna) Mavrično dominacijo na grafu $G$, z (neprazno) množico vozlišč in povezav ter množico s $k$ barvami, opišemo kot funkcijo $f$, ki vsako vozlišče označi s poljubno podmnožico barv tako, da imajo vsa tista vozlišča, ki jim je prirejena prazna množica, v svoji soseščini vseh $k$ barv. Funkciji $f$ tedaj pravimo $k$-mavrična dominantna funkcija grafa $G$. Vsota moči vseh oznak na vozliščih je vrednost $k$-mavrično dominantne funkcije. Najmanjša vrednost izmed vseh takih funkcij na grafu $G$ se imenuje $k$-mavrično dominantno število grafa $G$. V magistrskem delu podamo nekaj točnih vrednosti in zgornjih mej za $k$-mavrična dominantna števila. Večji poudarek damo na meje za 2- in 3-mavrično dominantna števila. Dokažemo dve splošni zgornji meji 2-mavrično dominantnega števila ter opišemo meje za 3-mavrično dominantna števila. Na koncu dela sledijo meje za $k$-mavrično dominantna števila, za katera je $k > 3$. V nekaterih primerih opišemo družine grafov, ki dosežejo enakost meje in jih dokažemo. Rainbow domination of a graph $G$, with a (non-empty) set of vertices and edges as well as a set with $k$ colors, is described as a function $f$, which assigns an arbitrary subset of colors to the vertices in such a way that for every vertex to which the empty set is assigned all $k$ colors appear in its neighbourhood. The corresponding function $f$ is a $k$-rainbow dominating function of the graph $G$. The sum of all the labels on the vertices is the value of the $k$-rainbow dominating function. The smallest value of all such functions on a graph $G$ is called the $k$-rainbow domination number of $G$. In the thesis, we give some exact values and upper bounds for $k$-rainbow domination numbers. More emphasis is placed on the bounds for 2- and 3-rainbow domination numbers. We prove two general upper bounds for 2-rainbow domination numbers and describe the bounds for 3-rainbow domination numbers. Finally, we present some bounds for $k$-rainbow domination numbers, where $k > 3$. In some cases we describe the families of graphs that achieve equality in the corresponding bound and provide necessary proofs. graf dominantno število mavrična dominantna funkcija mavrično dominantno število graph domination rainbow domination function rainbow domination number true true false [K. Zelko] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2022-12-29 11:56:41 2023-02-02 11:15:35 2023-02-03 03:05:39 0000-00-00 00:00:00 2023 0 Maribor 0 Maribor X, 36 f. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 140400387 EMAG_Zelko_Klavdija_2022.pdf EMAG_Zelko_Klavdija_2022.pdf 1 0BF2D83325EF40373BC4B9C1BC1EE5FB 06079f22d8587d9a53c06b3fb8eeae96c83adb55451a1af8abab853b3b446d30 af03b5b7-8846-11ed-944d-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=165029 Fakulteta za naravoslovje in matematiko 0 0 0