Chiraptophobic cockroaches evading a torch light

We propose and study game-theoretic versions of independence in graphs. The games are played by two players - the aggressor and the defender - taking alternate moves on a graph G with tokens located on vertices from an independent set of G. A move of the aggressor is to select a vertex v of G. A move of the defender is to move tokens located on vertices in NG(v) each along one incident edge. The goal of the defender is to maintain the set of occupied vertices independent while the goal of the aggressor is to make this impossible. We consider the maximum number of tokens for which the aggressor can not win in a strategic and an adaptive version of the game.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved