Grafi, ki dosežejo enakost v Vizingovi domnevi

magistrsko delo

Anamarija Lakner (Avtor), Boštjan Brešar (Mentor)

Povzetek

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 magistrskega dela 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 preglednici.

Ključne besede

magistrska dela;dominantno število;dominantna množica;Vizingova domneva;enakost v Vizingovi domnevi;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[A. Lakner]
UDK:	519.17(043.2)
COBISS:	127467779
Št. ogledov:	2
Št. prenosov:	0
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Graphs achieving the equality in vizing's conjecture
Sekundarni povzetek:	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 masters 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.
Sekundarne ključne besede:	master theses;domination number;domination set;Vizing’s conjecture;equality in Vizingʹs conjecture;Grafične metode;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:	VIII, 54 f.
ID:	16500831