Isolation Game on Graphs

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