Isolation Game on Graphs

Abstract Given a graph G and a family of graphs F F, an F F -isolating set, as introduced by Caro and Hansberg, is any set S V (G) S ⊂ V (G) such that G - NS G - N S contains no member of F F as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an F F -isolating set in G. Following the domination games, Dominator (Staller) wants that the resulting F 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 F F -isolation number, denoted g (G, F) ι g (G, F). We prove that the Continuation Principle holds in the F F -isolation game, and that the difference between the game F F -isolation numbers when either Dominator or Staller starts the game is at most 1. Considering two arbitrary families of graphs F F and F' F ′, we find relations between them that ensure g (G, {F}') g (G, {F}) ι g (G, F ′) ≤ ι g (G, F) for any graph G. A special focus is given on the isolation game, which takes place when F=\K₂\ <mml: math xmlns: mml="http