Domination games : PhD thesis

Iršič, Vesna (author), Klavžar, Sandi (mentor), Bujtás, Csilla (co-mentor)

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
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2021
• PID: 20.500.12556/RUL-131098
• UDC: 519.17
• COBISS.SI-ID: 78390787
• Publication date in RUL: 23.09.2021

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