On the Lengths of Symmetry Breaking-Preserving Games on Graphs

Abstract

Given a graph $G$, we consider a game where two players, $A$ and $B$, alternatingly color edges of $G$ in red and in blue respectively. Let $l(G)$ be the maximum number of moves in which $B$ is able to keep the red and the blue subgraphs isomorphic, if $A$ plays optimally to destroy the isomorphism. This value is a lower bound for the duration of any avoidance game on $G$ under the assumption that $B$ plays optimally. We prove that if $G$ is a path or a cycle of odd length $n$, then $\Omega (\log n)\le l(G)\le O({\log }^{2}n)$. The lower bound is based on relations with Ehrenfeucht games from model theory. We also consider complete graphs and prove that $l(K_n)=O(1)$.

20 pages