The oriented cycle game Original Research Article

Two players A and C play the following game on a graph G. They orient the edges of G alternately with C playing first until all the edges of G have been oriented. The goal of C is to create at least one oriented cycle, while A wants to avoid this and finish with an acyclic orientation. Among other results we determine the minimal integer m = m(n) such that C has a winning strategy on every graph of order n and size m. We also discuss several generalizations of this game.