Total isolation game in graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909983160926208 |
|---|---|
| author | Henning, Michael A. Rall, Douglas F. |
| author_facet | Henning, Michael A. Rall, Douglas F. |
| contents | The total isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $S$ is the set of already played vertices, then a vertex can be selected only if it is adjacent to a vertex that belongs to a (nontrivial) component of the graph $G - N_G(S)$ of order at least $2$ or a vertex that is isolated in $G - N_G(S)$ and belongs to the set $S$, where $N_G(S)$ is the set of vertices adjacent to a vertex in $S$. Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game total isolation number $ι_{\rm gt}(G)$ is the number of moves in the Dominator-start game where both players play optimally. We prove that if $G$ is a connected graph of order $n \ge 3$, then $ι_{\rm gt}(G) < \frac{5}{6}n$. Furthermore if $G$ has minimum degree at least $2$, then we prove that $ι_{\rm gt}(G) \le \frac{3}{4}n$. More generally, if $G$ is a connected graph of order $n \ge 3$ with minimum degree $δ$ where $δ\ge 2$, then we prove that $ι_{\rm gt}(G) \le \left( \frac{2δ-1}{3δ-2} \right) n$. Among other results it is proved that if $G$ is a graph of order $n$ with diameter $2$, then $ι_{\rm gt}(G) \le \frac{2}{3}n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03363 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Total isolation game in graphs Henning, Michael A. Rall, Douglas F. Combinatorics 05C65, 05C69 The total isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $S$ is the set of already played vertices, then a vertex can be selected only if it is adjacent to a vertex that belongs to a (nontrivial) component of the graph $G - N_G(S)$ of order at least $2$ or a vertex that is isolated in $G - N_G(S)$ and belongs to the set $S$, where $N_G(S)$ is the set of vertices adjacent to a vertex in $S$. Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game total isolation number $ι_{\rm gt}(G)$ is the number of moves in the Dominator-start game where both players play optimally. We prove that if $G$ is a connected graph of order $n \ge 3$, then $ι_{\rm gt}(G) < \frac{5}{6}n$. Furthermore if $G$ has minimum degree at least $2$, then we prove that $ι_{\rm gt}(G) \le \frac{3}{4}n$. More generally, if $G$ is a connected graph of order $n \ge 3$ with minimum degree $δ$ where $δ\ge 2$, then we prove that $ι_{\rm gt}(G) \le \left( \frac{2δ-1}{3δ-2} \right) n$. Among other results it is proved that if $G$ is a graph of order $n$ with diameter $2$, then $ι_{\rm gt}(G) \le \frac{2}{3}n$. |
| title | Total isolation game in graphs |
| topic | Combinatorics 05C65, 05C69 |
| url | https://arxiv.org/abs/2601.03363 |