Meje za mavrična dominantna števila

magistrsko delo

Klavdija Zelko (Avtor), Boštjan Brešar (Mentor)

Povzetek

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 in 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.

Ključne besede

magistrska dela;graf;dominantno število;mavrična dominantna funkcija;mavrično dominantno število;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2023
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[K. Zelko]
UDK:	519.17(043.2)
COBISS:	140400387
Št. ogledov:	35
Št. prenosov:	4
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Bounds on rainbow domination numbers
Sekundarni povzetek:	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.
Sekundarne ključne besede:	master theses;graph;domination;rainbow domination function;rainbow domination number;Grafične metode;Funkcije (matematika);Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	X, 36 f.
ID:	17550564