Neenakost Vizingovega tipa za različne dominacijske invariante

diplomsko delo

Vika Koban (Avtor), Boštjan Brešar (Mentor)

Povzetek

Dominacija na grafih je intenzivno raziskovana veja v teoriji grafov. Leta 1963 je Vizing postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov kvečjemu večje od produkta njunih dominantnih števil. Mnogo delnih rezultatov je bilo dokazanih, vendar pa je le-ta še vedno eden izmed največjih odprtih problemov v študiju dominacije na grafih. V tem diplomskem delu so v ospredju obravnavani najbolj znani izreki Vizingovega tipa za različne dominacijske invariante. Na začetku predstavimo nekaj dejstev o dominaciji na kartezičnem produktu. Opišemo znan Clark-Suenov rezultat Vizingovega tipa in t. i. razstavljive grafe, za katere Vizingova domneva drži. Drugi del se nanaša na pet dominacjiskih invariant; totalno, celoštevilsko, zgornjo, deljeno dominantno število in dominacijo po parih. Predstavljeni so izreki Vizingovega tipa za posamezne dominacijske parametre, kot na primer izrek za deljeno-dominantno število, Hojev izrek o totalnem dominantnem številu in izrek Vizingovega tipa za zgornje dominantno število.

Ključne besede

diplomska dela;matematika;dominantna množica;dominantno število;Vizingova domneva;dominacijske invariante;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2012
Izvor:	Maribor
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[V. Koban]
UDK:	51(043.2)
COBISS:	19318024
Št. ogledov:	1608
Št. prenosov:	208
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	VIZING-TYPE INEQUALITIES FOR VARIOUS DOMINATION GRAPH INVARIANTS
Sekundarni povzetek:	Domination in graphs is an extensively studied branch of graph theory. In 1963 Vizing conjectured that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers. Several partial results have been proven, but the conjecture still remains one of the biggest open problems in the study of domination in graphs. In the thesis our main focus are some of the most important variations of Vizing's conjecture for various domination-type invariants. At the beginning we explain some facts about domination in Cartesian products. We present famous Clark-Suen Vizing-type result and the so-called decomposable graphs, for which Vizing's conjecture is true. In the last part we survey versions for five main domination invariants; total, integer, upper, fractional and paired. Further on we describe Vizing-type theorems for several domination parameters, for instance theorem for fractional domination number, conjecture for total domination number solved by Ho and Vizing-type theorem for upper domination number.
Sekundarne ključne besede:	domination set;domination number;Vizing's conjecture;domination graph invariants;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	44 f.
Ključne besede (UDK):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	992654