Igre, porojene iz grafovske dominacije : doktorska disertacija

Košmrlj, Gašper (author), Klavžar, Sandi (mentor), Konvalinka, Matjaž (co-mentor)

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.

• Language: Slovenian
• Keywords: grafovska dominacija, dominacijska igra, igralno dominacijsko število, igre na grafih
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Place of publishing: Ljubljana
• Publisher: [G. Košmrlj]
• Year: 2015
• Number of pages: 101 str.
• PID: 20.500.12556/RUL-95856
• UDC: 519.17(043.3)
• COBISS.SI-ID: 17209177
• Publication date in RUL: 24.10.2017

Secondary language

• Language: English

Abstract

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.

• Keywords: graph domination, domination game, game domination number, games on graphs