Digital repository of Slovenian research organisations

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

Title:Indicated domination game
Authors:ID Brešar, Boštjan (Author)
ID Bujtás, Csilla (Author)
ID Iršič, Vesna (Author)
ID Rall, Douglas F. (Author)
ID Tuza, Zsolt (Author)
Files:.pdf PDF - Presentation file, download (367,70 KB)
MD5: F10A78E7791544EC8F8B69626B0D11B3
 
URL URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S0012365X24001912
 
Language:English
Typology:1.01 - Original Scientific Article
Organization:Logo IMFM - Institute of Mathematics, Physics, and Mechanics
Abstract:Motivated by the success of domination games and by a variation of the coloring game called the indicated coloring game, we introduce a version of domination games called the indicated domination game. It is played on an arbitrary graph $G$ by two players, Dominator and Staller, where Dominator wants to finish the game in as few rounds as possible while Staller wants just the opposite. In each round, Dominator indicates a vertex $u$ of $G$ that has not been dominated by previous selections of Staller, which, by the rules of the game, forces Staller to select a vertex in the closed neighborhood of $u$. The game is finished when all vertices of $G$ become dominated by the vertices selected by Staller. Assuming that both players are playing optimally according to their goals, the number of selected vertices during the game is the indicated domination number, $\gamma_{\rm i}(G)$, of $G$. We prove several bounds on the indicated domination number expressed in terms of other graph invariants. In particular, we find a place of the new graph invariant in the well-known domination chain, by showing that $\gamma_{\rm i}(G)\ge \Gamma(G)$ for all graphs $G$, and by showing that the indicated domination number is incomparable with the game domination number and also with the upper irredundance number. In connection with the trivial upper bound $\gamma_{\rm i}(G)\le n(G)-\delta(G)$, we characterize the class of graphs $G$ attaining the bound provided that $n(G)\ge 2\delta(G)+2$. We prove that in trees, split graphs and grids the indicated domination number equals the independence number. We also find a formula for the indicated domination number of powers of paths, from which we derive that there exist graphs in which the indicated domination number is arbitrarily larger than the upper irredundance number. We provide some partial results supporting the statement that $\gamma_{\rm i}(G)=n(G)/2$ if $G$ is a cubic bipartite graph, and leave this as an open question.
Keywords:domination game, indicated coloring, independence number, upper domination number
Publication status:Published
Publication version:Version of Record
Publication date:01.09.2024
Year of publishing:2024
Number of pages:10 str.
Numbering:Vol. 347, iss. 9, [article no.] 114060
PID:20.500.12556/DiRROS-18935 New window
UDC:519.17
ISSN on article:0012-365X
DOI:10.1016/j.disc.2024.114060 New window
COBISS.SI-ID:195595779 New window
Note:
Publication date in DiRROS:16.05.2024
Views:109
Downloads:87
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
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
Shortened title:Discrete math.
Publisher:North-Holland
ISSN:0012-365X
COBISS.SI-ID:1118479 New window

Document is financed by a project

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:P1-0297-2022
Name:Teorija grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-2452-2020
Name:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-3002-2021
Name:Prirejanja in barvanja povezav v kubičnih grafih

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:J1-4008-2022
Name:Drevesno neodvisnostno število grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0285-2023
Name:Metrični problemi v grafih in hipergrafih

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:N1-0218-2022
Name:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Funder:ARIS - Slovenian Research and Innovation Agency
Project number:Z1-50003-2023
Name:Igra policajev in roparja na grafih in geodetskih prostorih

Funder:EC - European Commission
Project number:101071836
Name:KARST: Predicting flow and transport in complex Karst systems
Acronym:KARST

Funder:Other - Other funder or multiple funders
Funding programme:National Research, Development and Innovation Office (Hungary)
Project number:SNN 129364

Funder:Other - Other funder or multiple funders
Funding programme:National Research, Development and Innovation Office (Hungary)
Project number:FK 132060

Licences

License:CC BY-NC 4.0, Creative Commons Attribution-NonCommercial 4.0 International
Link:http://creativecommons.org/licenses/by-nc/4.0/
Description:A creative commons license that bans commercial use, but the users don’t have to license their derivative works on the same terms.

Secondary language

Language:Slovenian
Keywords:dominacijska igra, indicirano barvanje, neodvisnostno število, zgornje dominantno število


Back