Meje za mavrična dominantna števila

magistrsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2023
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[K. Zelko]
UDC:	519.17(043.2)
COBISS:	140400387
Views:	35
Downloads:	4
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Bounds on rainbow domination numbers
Secondary abstract:	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.
Secondary keywords:	master theses;graph;domination;rainbow domination function;rainbow domination number;Grafične metode;Funkcije (matematika);Univerzitetna in visokošolska dela;
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	X, 36 f.
ID:	17550564