×

The oriented path game. (English) Zbl 1246.91026

The authors introduce what they call the oriented path game. This game is played by two players \(C\) (creator) and \(B\) (blocker) on a simple graph \(G\). The two players \(C\) and \(B\) will orient the edges of \(G\) alternating their turns with \(C\) starting the game. The goal of \(C\) is to create an oriented path of given length \(k\), whereas its \(B\)’s goal to prevent \(C\) from creating such path.
In their paper the authors discuss this game for \(k=3\). They determine, given optimal strategy, the winner for any possible graph, and show that if the graph is sufficiently dense \(C\) can always win the game.
The paper also determines the winner in the case where \(B\) starts the game (still for \(k=3\)).
In a last paragraph some results are mentioned on the case \(k=4\).

MSC:

91A43 Games involving graphs
05C57 Games on graphs (graph-theoretic aspects)
05C38 Paths and cycles