论文标题
树上的触摸器隔离器游戏
The Toucher-Isolator Game on Trees
论文作者
论文摘要
考虑以下由触摸器和隔离器在图$ g $的边缘上玩过的以下制造商 - 破坏者类型的游戏，并给予触摸器。隔离器的目的是最大化触摸器声称的任何边缘的顶点数量，而触摸器的目的是最大程度地减少此数字。让$ u \ left（g \ right）$为两个玩家最佳比赛时的隔离顶点的数量。 Dowden，Kang，Mikalački和Stojaković证明了$ \ weft \ lceil \ frac {n+2} {8} \ right \ rceil \ rceil \ rceil \ le \ le \ le \ left（t \ weled（t \ oyt） $ n $顶点。作者还证明了$ u \ left（p_ {n} \ right）= \ left \ lfloor \ frac {n+3} {5} {5} \ right \ rfloor $ for All $ n \ geq3 $，其中$ p_ {n} $是$ n $ vertices的路径。 本文的目的是将下限提高到$ u \ left（t \右）\ geq \ left \ lfloor \ frac {n+3} {5} {5} \ right \ rfloor $，这很尖锐。我们的结果可能被认为是说路径对于具有给定数量的顶点的树木中的隔离器是“最佳”。
Consider the following Maker-Breaker type game played by Toucher and Isolator on the edges of a graph $G$ with first move given to Toucher. The aim of Isolator is to maximise the number of vertices which are not incident to any edges claimed by Toucher, and the aim of Toucher is to minimise this number. Let $u\left(G\right)$ be the number of isolated vertices when both players play optimally. Dowden, Kang, Mikalački and Stojaković proved that $\left\lceil \frac{n+2}{8}\right\rceil \le u\left(T\right)\leq\left\lfloor \frac{n-1}{2}\right\rfloor $, where $T$ is a tree with $n$ vertices. The author also proved that $u\left(P_{n}\right)=\left\lfloor \frac{n+3}{5}\right\rfloor$ for all $n\geq3$, where $P_{n}$ is a path with $n$ vertices. The aim of this paper is to improve the lower bound to $u\left(T\right)\geq\left\lfloor \frac{n+3}{5}\right\rfloor$, which is sharp. Our result may be viewed as saying that paths are the 'best' for Isolator among trees with a given number of vertices.
