Digital repository of Slovenian research organisations

Show document
A+ | A- | Help | SLO | ENG

Title:Fast winning strategies for Staller in the Maker-Breaker domination game
Authors:ID Bujtás, Csilla (Author)
ID Dokyeesun, Pakanun (Author)
Files:.pdf PDF - Presentation file, download (503,82 KB)
MD5: 632DBA700A188F73A5DD64B3BCC8F945
 
URL URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0166218X23004286
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:The Maker-Breaker domination game is played on a graph G by two players, called Dominator and Staller, who alternately choose a vertex that has not been played so far. Dominator wins the game if his moves form a dominating set. Staller wins if she plays all vertices from a closed neighborhood of a vertex v∈V(G). Dominator's fast winning strategies were studied earlier. In this work, we concentrate on the cases when Staller has a winning strategy in the game. We introduce the invariant γ′SMB(G) (resp., γSMB(G)) which is the smallest integer k such that, under any strategy of Dominator, Staller can win the game by playing at most k vertices, if Staller (resp., Dominator) plays first on the graph G. We prove some basic properties of γSMB(G) and γ′SMB(G) and study the parameters' changes under some operators as taking the disjoint union of graphs or deleting a cut vertex. We show that the inequality δ(G)+1≤γ′SMB(G)≤γSMB(G) always holds and that for every three integers r,s,t with 2≤r≤s≤t, there exists a graph G such that δ(G)+1=r, γ′SMB(G)=s, and γSMB(G)=t. We prove exact formulas for γ′SMB(G) where G is a path, or it is a tadpole graph which is obtained from the disjoint union of a cycle and a path by adding one edge between them.
Keywords:domination game, Maker–Breaker game, winning number, Maker-Breaker domination game, closed neighborhood hypergraph
Publication status:Published
Publication version:Version of Record
Publication date:01.02.2024
Year of publishing:2024
Number of pages:str. 10-22
Numbering:Vol. 344
PID:20.500.12556/DiRROS-20509 New window
UDC:519.17
ISSN on article:0166-218X
DOI:10.1016/j.dam.2023.11.015 New window
COBISS.SI-ID:206680323 New window
Note:Spletna objava: 9. 11. 2023;
Publication date in DiRROS:03.10.2024
Views:397
Downloads:167
Metadata:XML DC-XML DC-RDF
:
BUJTÁS, Csilla and DOKYEESUN, Pakanun, 2024, Fast winning strategies for Staller in the Maker-Breaker domination game. Discrete applied mathematics [online]. 2024. Vol. 344, p. 10–22. [Accessed 21 April 2025]. DOI 10.1016/j.dam.2023.11.015. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=20509
Copy citation
  
Share:Bookmark and Share


Similar works from our repository:

No similar works found

Similar works from other repositories:

No similar works found

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete applied mathematics
Shortened title:Discrete appl. math.
Publisher:Elsevier
ISSN:0166-218X
COBISS.SI-ID:25342464 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0108
Name:Prenos naboja v grafovski dominaciji
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Back