We introduce a new positional game called `Toucher-Isolator', which is a quantitative version of a Maker-Breaker type game. The playing board is the set of edges of a given graph $G$, and the two players, Toucher and Isolator, claim edges alternately. The aim of Toucher is to `touch' as many vertices as possible (i.e. to maximise the number of vertices that are incident to at least one of her chosen edges), and the aim of Isolator is to minimise the number of vertices that are so touched. We analyse the number of untouched vertices $u(G)$ at the end of the game when both Toucher and Isolator play optimally, obtaining results both for general graphs and for particularly interesting classes of graphs, such as cycles, paths, trees, and $k$-regular graphs. We also provide tight examples.
@article{10_37236_8617,
author = {Chris Dowden and Mihyun Kang and Mirjana Mikala\v{c}ki and Milo\v{s} Stojakovi\'c},
title = {The toucher-isolator game},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {4},
doi = {10.37236/8617},
zbl = {1422.05069},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8617/}
}
TY - JOUR
AU - Chris Dowden
AU - Mihyun Kang
AU - Mirjana Mikalački
AU - Miloš Stojaković
TI - The toucher-isolator game
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/8617/
DO - 10.37236/8617
ID - 10_37236_8617
ER -
%0 Journal Article
%A Chris Dowden
%A Mihyun Kang
%A Mirjana Mikalački
%A Miloš Stojaković
%T The toucher-isolator game
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/8617/
%R 10.37236/8617
%F 10_37236_8617
Chris Dowden; Mihyun Kang; Mirjana Mikalački; Miloš Stojaković. The toucher-isolator game. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/8617
