TY - JOUR
AU - Matsumoto, Naoki
AU - Nagao, Atsuki
PY - 2023/12/31
Y2 - 2024/10/08
TI - Feedback Game on Eulerian Graphs: Discrete and Computational Geometry, Graphs, and Games
JF - Thai Journal of Mathematics
JA - Thai J Math
VL - 21
IS - 4
SE - Articles
DO -
UR - https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1542
SP - 751–768
AB - <p>In this paper, we introduce a two-player impartial game on graphs, called feedback game, which is a variant of generalized geography. Feedback game can be regarded as undirected edge geography with an additional rule that the first player who goes back to the starting vertex wins the game. We consider feedback game on an Eulerian graph since the game ends only by going back to the starting vertex. We first show that it is PSPACE-complete in general to determine the winner of the feedback game on Eulerian graphs even if its maximum degree is at most~4. In the latter half of the paper, we discuss the feedback game on two subclasses of Eulerian graphs, i.e., triangular grid graphs and toroidal grid graphs.</p>
ER -