2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Yoav Kallus
    Apr 24, 2012 at 20:30
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Uday
    Apr 24, 2012 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – Yoav Kallus
    Apr 24, 2012 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.