20.500.12556/DKUM-97415 Isolation game on graphs Izolacijska igra na grafih 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\}$▫. Za dani graf ▫$G$▫ in družino grafov ▫$\cal F$▫ je ▫$\cal F$▫-izolacijska množica poljubna taka množica ▫$S\subset V(G)$▫, za katero ▫$G - N[S]$▫ ne vsebuje grafa iz družine ▫$\cal F$▫ kot svojega podgrafa. Koncept sta vpeljala Caro in Hansberg. V tem članku vpeljemo igro na grafu, ki jo igrata dva igralca z nasprotnima ciljema, ki skupaj gradita ▫$\cal F$▫- izolacijsko množico grafa ▫$G$▫. Pri tem sledimo dominacijskim igram, tako da Dominator (Zavlačevalka) želi doseči, da je končna ▫$\cal F$▫-izolacijska množica karseda majhna (velika), kar pripelje do grafovske invariante poimenovane igralno ▫$\cal F$▫-izolacijsko število, ki jo označimo z ▫$\iota_{\rm g}(G,\cal F)$▫. Dokažemo, da tudi v ▫$\cal F$▫-izolacijski igri velja nadaljevalni princip in da je razlika med igralnim ▫$\cal F$▫-izolacijskim številom, ko igro začne bodisi Dominator bodisi Zavlačevalka, kvečjemu ▫$1$▫. Za družini grafov ▫$\cal F$▫ in ▫$\cal F'$▫ najdemo odnose med njima, ki zagotavljajo, da velja ▫$\iota_{\rm g}(G,{\mathcal{F}}') \leq \iota_{\rm g}(G,{\mathcal{F}})$▫ za vsak graf ▫$G$▫. Posebna pozornost je namenjena izolacijski igri za družino ▫${\cal F}=\{K_2\}$▫. Dokažemo, da velja ▫$\iota_{\rm g}(G,\{K_2\})\le |V(G)|/2$▫ za vsak graf ▫$G$▫ in postavimo domnevo, da je v tem primeru natančna zgornja meja ▫$\lceil 3|V(G)|/7\rceil$▫. Dokažemo, da v gozdovih izolacijska igra, v kateri začne Dominator, nikoli ni daljša od tiste, v kateri začne Zavlačevalka. Nazadnje dokažemo še dobre spodnje in zgornje meje za igralno izolacijsko število poti ▫$P_n$▫, ki vodijo do točnih vrednosti ▫$\iota_{\rm g}(P_n,\{K_2\})=\left\lfloor\frac{2n+2}{5}\right\rfloor$▫, v primeru ko ▫$n \equiv i \pmod 5$▫ in ▫$i \in \{1,2,3\}$▫. isolation number graph games domination games continuation principle forest izolacijsko število igre na grafih dominacijske igre nadaljevalni princip gozd true false true Springer Angleški jezik Slovenski jezik Znanstveno delo 2026-03-05 04:39:13 2026-09-10 14:43:55 2026-09-11 03:08:00 0000-00-00 00:00:00 2026 0 Tokyo 0 13 str. št. 2, št. članka 30 Letn. 42 Apr. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 2026-02-14 2026-03-03 519.17 270312963 10.1007/s00373-026-03030-y 0911-0119 RAZ_Bresar_Bostjan_2026.pdf RAZ_Bresar_Bostjan_2026.pdf 1 1D72F4EC4F8A03BE8A783F0727F62B54 265b611dabeccfdbe1b867030ea540313c9abde18536f183f964e360a86ccd3c 3bed4559-ad15-11f1-b668-00155d0001be https://dk.um.si/Dokument.php?lang=slv&id=212099 https://link.springer.com/article/10.1007/s00373-026-03030-y 1 e23d6b75-1844-11f1-b8bb-00155d580e1a https://dk.um.si/Dokument.php?lang=slv&id=204264 Fakulteta za naravoslovje in matematiko 0 0 0