Game on undirected graphs

One of my friends suggested the following 2-player game.

   Given an undirected graph(not necessarily connected), each player takes turns
and removes either one vertex or two adjacent vertices. Removing a vertex from
the graph consists of deleting the incident edges as well. The player who does
not have any move loses.


Though the rules of the game look very simple, this turns out to be an interesting counting and connectivity game. Infact, using symmetry argument, we have also found that there is a winning strategy for the second player when the undirected graph is merely an even length cycle.

The following are my questions:

Does any graph theory concept suggest this game? Is there a standard game of this sort? Can we come up with a winning strategy for any player for the general graph? My guess is this game may be a version of game of Nim over graphs, I am not sure though.

Thank you.

-

On any graph it is a combinatorial game which can be analyzed by the usual techniques. I can think of a few named cases.

If the graph is a path, it is called Kayles. Having it be a single cycle is the same with the added condition that the first player on their first move must choose from an end.

For a complete graph it is the subtraction game $S(1,2)$

A complete bipartite graph $K_{a,b}$ seems like a natural case.

-
A natural variation on the OP's game is to allow removal of any clique. It would not change the game for paths and cycles. For a union of complete graphs, it would be Nim. –  Yoav Kallus Apr 24 '12 at 20:30

There are some papers dealing with similar subjects. I googled now:

http://www.mathstat.dal.ca/~ottaway/VDel.pdf

http://www710.univ-lyon1.fr/~educhene/cv-Eric_fichiers/graphgames.pdf

The second one looks a bit similar to your game.

-
The second paper looks similar but the rules are a bit different. The players remove a vertex and all the neighboring vertices. May be there is a way to map the game in question to the one here. –  Uday Apr 24 '12 at 17:02
It seems like your game fits within the class of games the second paper describes as being equivalent to a "domination game": there is a finite set of moves (one for each vertex in the original graph plus one for each edge), a move can only be played once, and the set of available moves at subsequent turns strictly decreases. –  Yoav Kallus Apr 24 '12 at 20:28