izpis_h1_title_alt

Indicated domination game
ID Brešar, Boštjan (Avtor), ID Bujtás, Csilla (Avtor), ID Iršič, Vesna (Avtor), ID Rall, Douglas F. (Avtor), ID Tuza, Zsolt (Avtor)

.pdfPDF - Predstavitvena datoteka, prenos (352,00 KB)
MD5: FF6152119791A20AC9D686A62806E8A6
URLURL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0012365X24001912 Povezava se odpre v novem oknu

Izvleček
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.

Jezik:Angleški jezik
Ključne besede:domination game, indicated coloring, independence number, upper domination number
Vrsta gradiva:Članek v reviji
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FMF - Fakulteta za matematiko in fiziko
Status publikacije:Objavljeno
Različica publikacije:Objavljena publikacija
Leto izida:2024
Št. strani:10 str.
Številčenje:Vol. 347, iss. 9, art. 114060
PID:20.500.12556/RUL-156257 Povezava se odpre v novem oknu
UDK:519.17
ISSN pri članku:0012-365X
DOI:10.1016/j.disc.2024.114060 Povezava se odpre v novem oknu
COBISS.SI-ID:195595779 Povezava se odpre v novem oknu
Datum objave v RUL:16.05.2024
Število ogledov:63
Število prenosov:22
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Kopiraj citat
Objavi na:Bookmark and Share

Gradivo je del revije

Naslov:Discrete mathematics
Skrajšan naslov:Discrete math.
Založnik:Elsevier
ISSN:0012-365X
COBISS.SI-ID:1118479 Povezava se odpre v novem oknu

Licence

Licenca:CC BY-NC 4.0, Creative Commons Priznanje avtorstva-Nekomercialno 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc/4.0/deed.sl
Opis:Licenca Creative Commons, ki prepoveduje komercialno uporabo, vendar uporabniki ne rabijo upravljati materialnih avtorskih pravic na izpeljanih delih z enako licenco.

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:dominacijska igra, indicirano barvanje, neodvisnostno število, zgornje dominantno število

Projekti

Financer:Drugi - Drug financer ali več financerjev
Program financ.:National Research, Development and Innovation Office (NKFIH)
Številka projekta:SNN 129364

Financer:Drugi - Drug financer ali več financerjev
Program financ.:National Research, Development and Innovation Office (NKFIH)
Številka projekta:FK 132060

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:P1-0297
Naslov:Teorija grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-2452
Naslov:Strukturni, optimizacijski in algoritmični problemi v geometrijskih in topoloških predstavitvah grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-3002
Naslov:Prirejanja in barvanja povezav v kubičnih grafih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:J1-4008
Naslov:Drevesno neodvisnostno število grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0285
Naslov:Metrični problemi v grafih in hipergrafih

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:N1-0218
Naslov:Prepletanje geometrije, topologije in algebre v strukturni in topološki teoriji grafov

Financer:ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
Številka projekta:Z1-50003
Naslov:Igra policajev in roparja na grafih in geodetskih prostorih

Financer:EC - European Commission
Program financ.:ERC
Številka projekta:101071836
Akronim:KARST

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj