Igre, porojene iz grafovske dominacije

doktorska disertacija

Gašper Košmrlj (Avtor), Sandi Klavžar (Mentor), Matjaž Konvalinka (Komentor)

Povzetek

V delu preučujemo igre na grafih, ki temeljijo na dominaciji. Največ pozornosti posvetimo dominacijski igri, v kateri igralca dominator in zavlačevalka izmenično izbirata vozlišča končnega grafa, dokler izbrana vozlišča ne tvorijo dominacijske množice. Kot je jasno že iz imen igralcev, je dominatorjev cilj čim hitreje zaključiti igro, medtem ko zavlačevalka stremi k čim daljši igri. Igralno dominacijsko število grafa je invarianta, ki nam pove, koliko potez je potrebnih, ko oba igrata optimalno. Potem ko v prvem poglavju predstavimo zgodovino grafovske dominacije ter prve rezultate v povezavi z dominacijsko igro, se v drugem poglavju ukvarjamo z dominacijsko igro na disjunktni uniji grafov, v tretjem pa z igralnim dominacijskim številom na enostavnih družinah grafov. Četrto poglavje posvetimo realizacijam parov igralnega dominacijskega števila z visoko povezanimi družinami grafov, medtem ko v petem skonstruiramo neskončne razrede grafov, ki imajo igralno dominacijsko število (domnevno) maksimalno možno. V šestem poglavju rešimo klasični problem grafovskih invariant, in sicer, kako se invarianta poljubnega grafa spremeni, če mu odvzamemo eno povezavo ali eno vozlišče. V zadnjem poglavju nas zanimajo kombinatorne igre. Podrobneje si pogledamo kombinatorno različico dominacijske igre dom, za katero določimo Sprague-Grundyjeve vrednosti nekaterih enostavnih družin grafov.

Ključne besede

grafovska dominacija;dominacijska igra;igralno dominacijsko število;igre na grafih;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2015
Tipologija:	2.08 - Doktorska disertacija
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[G. Košmrlj]
UDK:	519.17(043.3)
COBISS:	17209177
Št. ogledov:	866
Št. prenosov:	391
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni povzetek:	In the thesis, we study games on graphs that are based on domination. Our main focus will be the domination game that is played by two players, Dominator and Staller, who are alternating in choosing vertices of a finite graph. The game ends when the set of chosen vertices forms a domination set. Dominator's goal is to finish the game in as few moves as possible, while Staller wants to delay the end of the game as long as she can. The total number of moves in the game, when both players are playing optimally, is called the game domination number. In the first chapter, we present the historical background of the domination theory in graphs, and introduce the domination game along with its first results. In Chapter 2, we study the domination game on disjoint unions of graphs, while Chapter 3 is used to present exact formulas for the game domination number of some simple classes of graphs. In the fourth chapter, we find highly connected families that realize all possible pairs of game domination numbers. In Chapter 5, we construct infinite families of 3/5-graphs and 3/5-trees, while Chapter 6 is used to solve a classical problem of graph invariants regarding edge and vertex removal. In the last chapter, we first present an overview of the similar combinatorial games, and then steer our attention towards the combinatorial game dom that has similar rules as the domination game. We compute Sprague-Grundy values for some simple families of graphs.
Sekundarne ključne besede:	graph domination;domination game;game domination number;games on graphs;
Vrsta dela (COBISS):	Doktorsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 3. stopnja
Strani:	101 str.
ID:	10865394