Geodesic
Creating spanning trees in Waiter-Client games
Grzegorz Adamski1 ; Sylwia Antoniuk1 ; Małgorzata Bednarska-Bzdęga1 ; Dennis Clemens2 ; Fabian Hamann2 ; Yannick Mogge2
1Adam Mickiewicz University
2Hamburg University of Technology
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/12957
Classification : 91A43, 91A24, 05C05, 05C57

Grzegorz Adamski  1   ; Sylwia Antoniuk  1   ; Małgorzata Bednarska-Bzdęga  1   ; Dennis Clemens  2   ; Fabian Hamann  2   ; Yannick Mogge  2

1 Adam Mickiewicz University
2 Hamburg University of Technology 
@article{10_37236_12957,
     author = {Grzegorz Adamski and Sylwia Antoniuk and Ma{\l}gorzata Bednarska-Bzd\k{e}ga and Dennis Clemens and Fabian Hamann and Yannick Mogge},
     title = {Creating spanning trees in {Waiter-Client} games},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/12957},
     zbl = {8097663},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12957/}
}
TY  - JOUR
AU  - Grzegorz Adamski
AU  - Sylwia Antoniuk
AU  - Małgorzata Bednarska-Bzdęga
AU  - Dennis Clemens
AU  - Fabian Hamann
AU  - Yannick Mogge
TI  - Creating spanning trees in Waiter-Client games
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12957/
DO  - 10.37236/12957
ID  - 10_37236_12957
ER  - 
%0 Journal Article
%A Grzegorz Adamski
%A Sylwia Antoniuk
%A Małgorzata Bednarska-Bzdęga
%A Dennis Clemens
%A Fabian Hamann
%A Yannick Mogge
%T Creating spanning trees in Waiter-Client games
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12957/
%R 10.37236/12957
%F 10_37236_12957
Grzegorz Adamski; Sylwia Antoniuk; Małgorzata Bednarska-Bzdęga; Dennis Clemens; Fabian Hamann; Yannick Mogge. Creating spanning trees in Waiter-Client games. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/12957

Cité par Sources :