| Naslov: | Isolation game on graphs |
|---|
| Avtorji: | ID Brešar, Boštjan (Avtor)
ID Dravec, Tanja (Avtor)
ID Johnston, Daniel P. (Avtor)
ID Kuenzel, Kirsti (Avtor)
ID Rall, Douglas F. (Avtor) |
|---|
| Datoteke: |  RAZ_Bresar_Bostjan_2026.pdf (298,29 KB)
MD5: 1D72F4EC4F8A03BE8A783F0727F62B54
 https://link.springer.com/article/10.1007/s00373-026-03030-y
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | Given a graph ▫$G$▫ and a family of graphs ▫$\cal F$▫, an ▫$\cal F$▫-isolating set, as introduced by Caro and Hansberg, is any set ▫$S\subset V(G)$▫ such that ▫$G - N[S]$▫ contains no member of ▫$\cal F$▫ as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an ▫$\cal F$▫-isolating set in ▫$G$▫. Following the domination games, Dominator (Staller) wants that the resulting ▫$\cal F$▫-isolating set obtained at the end of the game, is as small (as big) as possible, which leads to the graph invariant called the game ▫$\cal F$▫-isolation number, denoted ▫$\iota_{\rm g}(G,\cal F)$▫. We prove that the Continuation Principle holds in the ▫$\cal F$▫-isolation game, and that the difference between the game ▫$\cal F$▫-isolation numbers when either Dominator or Staller starts the game is at most ▫$1$▫. Considering two arbitrary families of graphs ▫$\cal F$▫ and ▫$\cal F'$▫, we find relations between them that ensure ▫$\iota_{\rm g}(G,{\mathcal{F}}') \leq \iota_{\rm g}(G,{\mathcal{F}})$▫ for any graph ▫$G$▫. A special focus is given on the isolation game, which takes place when ▫${\cal F}=\{K_2\}$▫. We prove that ▫$\iota_{\rm g}(G,\{K_2\})\le |V(G)|/2$▫ for any graph ▫$G$▫, and conjecture that ▫$\lceil 3|V(G)|/7\rceil$▫ is the actual (sharp) upper bound. We prove that the isolation game on a forest when Dominator has the first move never lasts longer than the one in which Staller starts the game. Finally, we prove good lower and upper bounds on the game isolation numbers of paths ▫$P_n$▫, which lead to the exact values ▫$\iota_{\rm g}(P_n,\{K_2\})=\left\lfloor\frac{2n+2}{5}\right\rfloor$▫ when ▫$n \equiv i \pmod 5$▫ and ▫$i \in \{1,2,3\}$▫. |
|---|
| Ključne besede: | isolation number, graph games, domination games, continuation principle, forest |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum sprejetja članka: | 14.02.2026 |
|---|
| Datum objave: | 03.03.2026 |
|---|
| Kraj izida: | Tokyo |
|---|
| Založnik: | Springer |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 13 str. |
|---|
| Številčenje: | Letn. 42, št. 2, št. članka 30 |
|---|
| PID: | 20.500.12556/DKUM-97415  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 270312963 |
|---|
| DOI: | 10.1007/s00373-026-03030-y |
|---|
| ISSN pri članku: | 0911-0119 |
|---|
| Datum objave v DKUM: | 10.09.2026 |
|---|
| Število ogledov: | 195 |
|---|
| Število prenosov: | 0 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
