| Naslov: | Bounds on the game isolation number and exact values for paths and cycles |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Dravec, Tanja (Avtor)
ID Henning, Michael A. (Avtor)
ID Klavžar, Sandi (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (416,35 KB)
MD5: 2ACD69B2C51D44023D5F9D8BEE74C84A
 URL - Izvorni URL, za dostop obiščite https://dmtcs.episciences.org/18488
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | isolating set, isolation game, paths and cycles, trees |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 22 str. |
|---|
| Številčenje: | Vol. 28, no. 2 article no. 33 |
|---|
| PID: | 20.500.12556/DiRROS-30029  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 1365-8050 |
|---|
| DOI: | 10.46298/dmtcs.16132 |
|---|
| COBISS.SI-ID: | 281382915 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 12.06.2026 |
|---|
| Število ogledov: | 80 |
|---|
| Število prenosov: | 67 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
