On the Lengths of Symmetry Breaking-Preserving Games on Graphs
| dc.creator | Harary, Frank | |
| dc.creator | Slany, Wolfgang | |
| dc.creator | Verbitsky, Oleg | |
| dc.date | 2004-01-26 | |
| dc.date.accessioned | 2026-07-07T05:04:53Z | |
| dc.date.available | 2026-07-07T05:04:53Z | |
| dc.description | 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 $Ω(\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)$. | |
| dc.description | 20 pages | |
| dc.identifier | https://arxiv.org/abs/math/0401363 | |
| dc.identifier | http://arxiv.org/abs/math/0401363 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69979 | |
| dc.subject | Combinatorics | |
| dc.subject | Logic | |
| dc.subject | 05C38; 90D42 | |
| dc.title | On the Lengths of Symmetry Breaking-Preserving Games on Graphs | |
| dc.type | text |