On the Lengths of Symmetry Breaking-Preserving Games on Graphs

Details On the Lengths of Symmetry Breaking-Preserving Games on Graphs On the Lengths of Symmetry Breaking-Preserving Games on Graphs

2004-01-26

arxiv.org/abs/math/0401363v1

Mathematics

Combinatorics

20 pages

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

On the Lengths of Symmetry Breaking-Preserving Games on Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Lengths of Symmetry Breaking-Preserving Games on Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Lengths of Symmetry Breaking-Preserving Games on Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-143478