Bounds on the game isolation number and exact values for paths and cycles

Bujtás, Csilla (avtor), Dravec, Tanja (avtor), Henning, Michael A. (avtor), Klavžar, Sandi (avtor)

The isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $X$ is the set of already played vertices, then a vertex can be selected only if it dominates a vertex from a nontrivial component of $G \setminus N_G[X]$, where $N_G[X]$ is the set of vertices in $X$ or adjacent to a vertex in $X$. Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game isolation number $\iota_{\rm g}(G)$ is the number of moves in the Dominator-start game where both players play optimally. If Staller starts the game the invariant is denoted by $\iota_{\rm g}'(G)$. In this paper, $\iota_{\rm g}(C_n)$, $\iota_{\rm g}(P_n)$, $\iota_{\rm g}'(C_n)$, and $\iota_{\rm g}'(P_n)$ are determined for all $n$. It is proved that there are only two graphs that attain equality in the upper bound $\iota_{\rm g}(G) \le \frac{1}{2}|V(G)|$, and that there are precisely eleven graphs which attain equality in the upper bound $\iota_{\rm g}'(G) \le \frac{1}{2}|V(G)|$. For trees $T$ of order at least three it is proved that $\iota_{\rm g}(T) \le \frac{5}{11}|V(T)|$. A new infinite family of graphs $G$ is also constructed for which $\iota_{\rm g}(G) = \iota_{\rm g}'(G) = \frac{3}{7}|V(G)|$ holds.

• Jezik: Angleški jezik
• Ključne besede: isolating set, isolation game, paths and cycles, trees
• 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: 2026
• Št. strani: 22 str.
• Številčenje: Vol. 28, no. 2 art. 33
• PID: 20.500.12556/RUL-183402
• UDK: 519.17
• ISSN pri članku: 1365-8050
• DOI: 10.46298/dmtcs.16132
• COBISS.SI-ID: 281382915
• Datum objave v RUL: 12.06.2026

Gradivo je del revije

• Naslov: Discrete mathematics & theoretical computer science
• Skrajšan naslov: Discret. math. theor. comput. sci.
• Založnik: DMTCS
• ISSN: 1365-8050
• COBISS.SI-ID: 8089433

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: izolacijska množica, izolacijska igra, poti in cikli, drevesa