20.500.12556/RUL-156257 Indicated domination game 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. domination game indicated coloring independence number upper domination number dominacijska igra indicirano barvanje neodvisnostno število zgornje dominantno število true false true Angleški jezik Slovenski jezik Članek v reviji 2024-05-16 10:05:37 2024-05-16 10:05:43 2024-06-17 12:58:25 0000-00-00 00:00:00 2024 0 0 10 str. iss. 9, art. 114060 Vol. 347 Sep. 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0012-365X 10.1016/j.disc.2024.114060 195595779 1-s2.0-S0012365X24001912-main.pdf 1-s2.0-S0012365X24001912-main.pdf 1 FF6152119791A20AC9D686A62806E8A6 49131d6afc99c72535315b0c8d3e4673a913f35da0f87ba4a24077086c3114e4 398fd5a4-1e54-11ef-b1e4-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=185734 https://www.sciencedirect.com/science/article/pii/S0012365X24001912 1 17a14f12-135b-11ef-bd09-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=183617 Fakulteta za matematiko in fiziko 0 0 0