Creating spanning trees in Waiter-Client games

التفاصيل البيبلوغرافية
العنوان: Creating spanning trees in Waiter-Client games
المؤلفون: Adamski, Grzegorz, Antoniuk, Sylwia, Bednarska-Bzdęga, Małgorzata, Clemens, Dennis, Hamann, Fabian, Mogge, Yannick
سنة النشر: 2024
المجموعة: Mathematics
مصطلحات موضوعية: Mathematics - Combinatorics, 05C05, 91A24
الوصف: For a positive integer $n$ and a tree $T_n$ on $n$ vertices, we consider an unbiased Waiter-Client game $\textrm{WC}(n,T_n)$ played on the complete graph~$K_n$, in which Waiter's goal is to force Client to build a copy of $T_n$. We prove that for every constant $c<1/3$, if $\Delta(T_n)\le cn$ and $n$ is sufficiently large, then Waiter has a winning strategy in $\textrm{WC}(n,T_n)$. On the other hand, we show that there exist a positive constant $c'<1/2$ and a family of trees $T_{n}$ with $\Delta(T_n)\le c'n$ such that Client has a winning strategy in the $\textrm{WC}(n,T_n)$ game for every $n$ sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.
نوع الوثيقة: Working Paper
الوصول الحر: http://arxiv.org/abs/2403.18534Test
رقم الانضمام: edsarx.2403.18534
قاعدة البيانات: arXiv