Mathematics – Combinatorics
Scientific paper
2009-10-22
Mathematics
Combinatorics
Scientific paper
We analyze the duration of the unbiased Avoider-Enforcer game for three basic positional games. All the games are played on the edges of the complete graph on $n$ vertices, and Avoider's goal is to keep his graph outerplanar, diamond-free and $k$-degenerate, respectively. It is clear that all three games are Enforcer's wins, and our main interest lies in determining the largest number of moves Avoider can play before losing. Extremal graph theory offers a general upper bound for the number of Avoider's moves. As it turns out, for all three games we manage to obtain a lower bound that is just an additive constant away from that upper bound. In particular, we exhibit a strategy for Avoider to keep his graph outerplanar for at least $2n-8$ moves, being just 6 short of the maximum possible. A diamond-free graph can have at most $d(n)=\lceil\frac{3n-5}{2}\rceil$ edges, and we prove that Avoider can play for at least $d(n)-3$ moves. Finally, if $k$ is small compared to $n$, we show that Avoider can keep his graph $k$-degenerate for as many as $e(n)$ moves, where $e(n)$ is the maximum number of edges a $k$-degenerate graph can have.
Barát János
Stojaković Miloš
No associations
LandOfFree
On winning fast in Avoider-Enforcer games 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 winning fast in Avoider-Enforcer games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On winning fast in Avoider-Enforcer games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-422991