Games without repetitions on trees and multitrees (Q1312356)

We consider two-person games of the type NIM on a simple graph, where each edge may be used at most once during the playing of the game. We solve a certain problem of game partition into winning and losing vertices in the class of trees and multi-trees. The characterization of trees in which each vertex is a winning position is given. Moreover, we present an algorithm finding the game partition of a tree. Finally, we show that the game partition problem for multi-trees can be reduced to certain trees.