The Toucher-Isolator game

Abstract

© The authors. All rights reserved. We introduce a new positional game called `Toucher-Isolator', which is a quan-titative version of a Maker-Breaker type game. The playing board is the set ofedges of a given graph G, and the two players, Toucher and Isolator, claim edgesalternately. The aim of Toucher is to `touch' as many vertices as possible (i.e. tomaximise the number of vertices that are incident to at least one of her chosenedges), and the aim of Isolator is to minimise the number of vertices that are sotouched.We analyse the number of untouched vertices u(G) at the end of the game whenboth Toucher and Isolator play optimally, obtaining results both for general graphsand for particularly interesting classes of graphs, such as cycles, paths, trees, andk-regular graphs. We also provide tight examples.