





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。