A two-person game on graphs where each player tries to encircle his opponent's men

We present results on a combinatorial game which was proposed to one of the authors by Ingo Althofer (personal communication). Let G be an undirected finite graph without loops and multiple edges and let k be a positive integ er with k less than or equal to 1/2(\G\ -1). There are two players, called white and black, both having k men of their color. In turn, beginning with white, the players position their men one at a time on unoccupied vertices of G. When all men are placed, the players take turns moving a man of their color along an edge to an unoccupied adjacent vertex (again beginning with white). A player wins if his opponent cannot carry out his next move since none of his men has an unoccupied neighbor. If the game does not stop, the n the outcome is a draw. We always assume that both players play optimal. A mong other questions, we deal with the following ones: 1. Is it true that, for all G and k, white cannot win the game? 2. Does there exist a tree T an d a positive integer k for which the outcome is a draw? Let tau(G) denote t he covering number of G, i.e., tau(G) is the minimum number of vertices cov ering all edges of G. We prove that black wins the game if tau(G)less than or equal to k. We use this result to show that white never wins the game if G is bipartite, thus providing a partial answer to the first question. We answer the second question in the affirmative by constructing an infinite s eries of trees for which the outcome is a draw (for some k). Moreover, we p resent results on extremal problems arising in the context of the game. We also completely solve the cases when G is a path or a cycle. Further, we co mpletely settle the case k less than or equal to 2. In the proofs of our re sults, matchings and cycles in graphs play a predominant role. (C) 1999-Els evier Science B.V. All rights reserved.