Creating spanning trees in Waiter-Client games

2024/03/27 by Grzegorz Adamski, Adamski, Grzegorz, Sylwia Antoniuk +9
Computer Science · Social Sciences · #05C05 #91A24 #Combinatorics (math.CO) #Digital Games and Media #FOS: Mathematics #Peer-to-Peer Network Technologies

paper · pdf · doi:10.48550/arxiv.2403.18534

openalex publication_date 2024/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For a positive integer n and a tree T_n on n vertices, we consider an unbiased Waiter-Client game \textrmWC(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 Δ(T_n)≤ cn and n is sufficiently large, then Waiter has a winning strategy in \textrmWC(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 Δ(T_n)≤ c'n such that Client has a winning strategy in the \textrmWC(n,T_n) game for every n sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.

Related

• Creating spanning trees in waiter-client games
• On the connectivity Waiter-Client game
• Fast strategies in waiter-client games
• Client-Waiter games on complete and random graphs
• Waiter-Client Clique-Factor Game