Neenakost Vizingovega tipa za različne dominacijske invariante

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2012
Source:	Maribor
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[V. Koban]
UDC:	51(043.2)
COBISS:	19318024
Views:	1608
Downloads:	208
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	VIZING-TYPE INEQUALITIES FOR VARIOUS DOMINATION GRAPH INVARIANTS
Secondary abstract:	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.
Secondary keywords:	domination set;domination number;Vizing's conjecture;domination graph invariants;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	44 f.
Keywords (UDC):	mathematics;natural sciences;naravoslovne vede;matematika;mathematics;matematika;
ID:	992654