On the two problems in Ramsey achievement games

Abstract

Let $p,q$ be two integers with $p\ge q$. Given a finite graph $F$ with no isolated vertices, the generalized Ramsey achievement game of $F$ on the complete graph $K_n$, denoted by $(p,q;K_n,F,+)$, is played by two players called Alice and Bob. In each round, Alice firstly chooses $p$ uncolored edges $e_1,e_2,...,e_p$ and colors it blue, then Bob chooses $q$ uncolored edge $f_1,f_2,...,f_q$ and colors it red; the player who can first complete the formation of $F$ in his (or her) color is the winner. The generalized achievement number of $F$, denoted by $a(p,q;F)$ is defined to be the smallest $n$ for which Alice has a winning strategy. If $p=q=1$, then it is denoted by $a(F)$, which is the classical achievement number of $F$ introduced by Harary in 1982. If Alice aims to form a blue $F$, and the goal of Bob is to try to stop him, this kind of game is called the first player game by Bollobás. Let $a^{\ast }(F)$ be the smallest positive integer $n$ for which Alice has a winning strategy in the first player game. A conjecture due to Harary states that the minimum value of $a(T)$ is realized when $T$ is a path and the maximum value of $a(T)$ is realized when $T$ is a star among all trees $T$ of order $n$. He also asked which graphs $F$ satisfy $a^{\ast }(F)=a(F)$? In this paper, we proved that $n\le a(p,q;T)\le n+q\lfloor (n-2)/p\rfloor$ for all trees $T$ of order $n$, and obtained a lower bound of $a(p,q;K_{1,n-1})$, where $K_{1,n-1}$ is a star. We proved that the minimum value of $a(T)$ is realized when $T$ is a path which gives a positive solution to the first part of Harary's conjecture, and $a(T)\le 2n-2$ for all trees of order $n$. We also proved that for $n\ge 3$, we have $2n-2-\sqrt{(4n-8)\ln (4n-4)}\le a(K_{1,n-1})\le 2n-2$ with the help of a theorem of Alon, Krivelevich, Spencer and Szabó. We proved that $a^{\ast }(P_n)=a(P_n)$ for a path $P_n$.

13 pages