EUVIMEDEUVIMED entdecken
Crossref

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

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

Discrete Mathematics & Theoretical Computer Science · 12.06.2026 · vol. 28:2 (Graph Theory)

DOI: 10.46298/dmtcs.16132 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 12.06.2026. Verfasst von Csilla Bujtás und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Bujtás, C., Dravec, T., Henning, M. A., & Klavžar, S. (2026). Bounds on the game isolation number and exact values for paths and cycles. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.16132

Vancouver

Bujtás C, Dravec T, Henning MA, Klavžar S. Bounds on the game isolation number and exact values for paths and cycles. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.16132

BibTeX
@article{Bujts2026,
  author = {Bujtás, Csilla and Dravec, Tanja and Henning, Michael A. and Klavžar, Sandi},
  title = {Bounds on the game isolation number and exact values for paths and cycles},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:2},
  number = {Graph Theory},
  doi = {10.46298/dmtcs.16132}
}
Kostenlos starten →