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

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

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.

• Language: English
• Keywords: isolating set, isolation game, paths and cycles, trees
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: 22 str.
• Numbering: Vol. 28, no. 2 art. 33
• PID: 20.500.12556/RUL-183402
• UDC: 519.17
• ISSN on article: 1365-8050
• DOI: 10.46298/dmtcs.16132
• COBISS.SI-ID: 281382915
• Publication date in RUL: 12.06.2026

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

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: izolacijska množica, izolacijska igra, poti in cikli, drevesa