Loading [MathJax]/jax/output/HTML-CSS/jax.js
Digital repository of Slovenian research organisations

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

Title:Maker-Breaker domination game on trees when Staller wins
Authors:ID Bujtás, Csilla (Author)
ID Dokyeesun, Pakanun (Author)
ID Klavžar, Sandi (Author)
Files:.pdf PDF - Presentation file, download (255,58 KB)
MD5: D9ABDC296CA33CAD76EB9FE4F838BFE7
 
URL URL - Source URL, visit https://dmtcs.episciences.org/12202
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:In the Maker-Breaker domination game played on a graph G, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then γSMB(G) (resp., γ′SMB(G)) denotes the minimum number of moves Staller needs to win. For every positive integer k, trees T with γ′SMB(T)=k are characterized and a general upper bound on γ′SMB is proved. Let S=S(n1,…,nℓ) be the subdivided star obtained from the star with ℓ edges by subdividing its edges n1−1,…,nℓ−1 times, respectively. Then γ′SMB(S) is determined in all the cases except when ℓ≥4 and each ni is even. The simplest formula is obtained when there are at least two odd nis. If n1 and n2 are the two smallest such numbers, then γ′SMB(S(n1,…,nℓ))=⌈log2(n1+n2+1)⌉▫. For caterpillars, exact formulas for γSMB and for γ′SMB are established.
Keywords:domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars
Publication status:Published
Publication version:Version of Record
Publication date:01.01.2023
Year of publishing:2023
Number of pages:21 str.
Numbering:Vol. 25, no. 2, [article no.] 12
PID:20.500.12556/DiRROS-18631 New window
UDC:519.17
ISSN on article:1365-8050
DOI:10.46298/dmtcs.10515 New window
COBISS.SI-ID:164065283 New window
Note:
Publication date in DiRROS:08.04.2024
Views:905
Downloads:342
Metadata:XML DC-XML DC-RDF
:
BUJTÁS, Csilla, DOKYEESUN, Pakanun and KLAVŽAR, Sandi, 2023, Maker-Breaker domination game on trees when Staller wins. Discrete mathematics & theoretical computer science [online]. 2023. Vol. 25, no. 2,  12. [Accessed 11 April 2025]. DOI 10.46298/dmtcs.10515. Retrieved from: https://dirros.openscience.si/IzpisGradiva.php?lang=eng&id=18631
Copy citation
  
Share:Bookmark and Share


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 mathematics & theoretical computer science
Shortened title:Discret. math. theor. comput. sci.
Publisher:DMTCS
ISSN:1365-8050
COBISS.SI-ID:8089433 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297
Name:Teorija grafov
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-2452
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov
Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285
Name:Metrični problemi v grafih in hipergrafih
Funder:Other - Other funder or multiple funders
Funding programme:The Institute for the Promotion of Teaching Science and Technology (IPST), Thailand
Name:PhD scholarship

Licences

License:CC BY 4.0, Creative Commons Attribution 4.0 International
Link:http://creativecommons.org/licenses/by/4.0/
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

Language:Slovenian
Keywords:dominacijska igra, igra izdelovalec-lomilec, dominacijska igra izdelovalec-lomilec, hipergrafi, drevesa, subdividirane zvezde, gosenice


Back