Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Bounds on the game i ...
Article

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

Csilla Bujtás ORCID (1) (2), Tanja Dravec ORCID (3) (2), Michael A. Henning ORCID (4), Sandi Klavžar ORCID (1) (2) (3)
(1) University of Ljubljana [UL]
(2) Institute of Mathematics, Physics, and Mechanics [IMFM]
(3) University of Maribor
(4) University of Johannesburg [UJ]
Download article
Open on arXiv
Submitted on
July 29, 2025
Accepted on
May 25, 2026
Published on
June 12, 2026
Last modified on
June 12, 2026
Volume 28
vol. 28:2
Graph Theory
DOI
10.46298/dmtcs.16132
License
Attribution 4.0 International (CC BY 4.0)
Indicators
252
Views
138
Downloads

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

Csilla Bujtás ORCID (1) (2), Tanja Dravec ORCID (3) (2), Michael A. Henning ORCID (4), Sandi Klavžar ORCID (1) (2) (3)
(1) University of Ljubljana [UL]
(2) Institute of Mathematics, Physics, and Mechanics [IMFM]
(3) University of Maribor
(4) University of Johannesburg [UJ]
Abstract
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 $ι_{\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 $ι_{\rm g}'(G)$. In this paper, $ι_{\rm g}(C_n)$, $ι_{\rm g}(P_n)$, $ι_{\rm g}'(C_n)$, and $ι_{\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 $ι_{\rm g}(G) \le \frac{1}{2}|V(G)|$, and that there are precisely eleven graphs which attain equality in the upper bound $ι_{\rm g}'(G) \le \frac{1}{2}|V(G)|$. For trees $T$ of order at least three it is proved that $ι_{\rm g}(T) \le \frac{5}{11}|V(T)|$. A new infinite family of graphs $G$ is also constructed for which $ι_{\rm g}(G) = ι_{\rm g}'(G) = \frac{3}{7}|V(G)|$ holds.
Keywords
  • Combinatorics
Preview
Loading PDF preview...