izpis_h1_title_alt

Domination games : PhD thesis
ID Iršič, Vesna (Author), ID Klavžar, Sandi (Mentor) More about this mentor... This link opens in a new window, ID Bujtás, Csilla (Comentor)

.pdfPDF - Presentation file, Download (1,65 MB)
MD5: 3DBD5EA9F49F1708689DACFAC012432A

Abstract
In the last decade, domination games have received an increasing amount of attention. In the basic version of the game, two players, Dominator and Staller, take turns to dominate vertices of a graph. Dominator aims to minimize the number of moves while Staller aims to maximize the number of moves. If both players play optimally, the number of moves is a graph invariant called the game domination number of the graph. In this thesis, we focus on the domination game and its variations total domination game, Z-domination game, and connected domination game. We discuss Rall's $1/2$-conjecture for the domination game and provide several partial results to support it. We also investigate a general upper bound for the game domination number. We introduce perfect graphs for domination and total domination games, and present their characterizations, along with several other results. For the total domination game we study the effect of predomination and vertex removal. In particular, we resolve the predomination case. Both Z-domination game and connected domination game have been introduced only recently. We compare the length of the Z-domination game with other domination games and focus on equality cases. For the connected domination game we present several new results, including the solution of the game on lexicographic products, several results on Cartesian products, and the relationship between Dominator- and Staller-start game.

Language:English
Keywords:domination in graphs, domination game, total domination game, Z-domination game, connected domination game
Work type:Doctoral dissertation
Typology:2.08 - Doctoral Dissertation
Organization:FMF - Faculty of Mathematics and Physics
Year:2021
PID:20.500.12556/RUL-131098 This link opens in a new window
UDC:519.17
COBISS.SI-ID:78390787 This link opens in a new window
Publication date in RUL:23.09.2021
Views:2395
Downloads:351
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:Slovenian
Title:Dominacijske igre
Abstract:
V zadnjem desetletju so dominacijske igre deležne vedno večje pozornosti. V osnovni različici igre dva igralca, Dominator in Zavlačevalka, izmenično dominirata vozlišča grafa. Dominatorjev cilj je doseči čim manjše skupno število potez, Zavlačevalka pa se trudi igro podaljšati. Če oba igralca igrata optimalno, je število potez invarianta grafa, ki se imenuje igralno dominantno število grafa. V tezi se osredotočimo na dominacijsko igro in njeno celotno, Z- in povezano različico. Razpravo o Rallovi 1/2-domnevi za dominacijsko igro podkrepimo s številnimi delnimi rezultati, ter raziščemo splošno zgornjo mejo za igralno dominantno število. Vpeljemo popolne grafe za dominacijsko in celotno dominacijsko igro ter jih karakteriziramo. Hkrati predstavimo tudi nekatere dodatne rezultate. Študiramo vpliv predominacije in odstranitve vozlišča na igralno celotno dominantno število. Med drugim razrešimo vprašanja o vplivu predominacije. Tako Z-dominacijska igra kot povezana dominacijska igra sta bili vpeljani šele nedavno. Dolžino Z-dominacijske igre primerjamo z ostalimi dominacijskimi igrami in se posvetimo primerom enakosti. Predstavimo tudi nove rezultate za povezano dominacijsko igro, med drugim razrešitev igre na leksikografskih produktih, rezultate na kartezičnih produktih in razliko med igro, kjer prvo potezo naredi Dominator ali Zavlačevalka.

Keywords:dominacija na grafih, dominacijska igra, celotna dominacijska igra, Z-dominacijska igra, povezana dominacijska igra

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back