Now showing1 - 1 of 1
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Creating spanning trees in waiter-client games(Australian National University, 2025-08-22); ; ; For a positive integer n and a tree Tn on n vertices, we consider an unbiased Waiter-Client game WC(n, Tn) played on the complete graph Kn, in which Waiterâs goal is to force Client to build a copy of Tn. We prove that for every constant c < 1/3, if â(Tn) †cn and n is sufficiently large, then Waiter has a winning strategy in WC(n, Tn). On the other hand, we show that there exist a positive constant câČ < 1/2 and a family of trees Tn with â(Tn) †câČn such that Client has a winning strategy in the WC(n, Tn) game for every n sufficiently large. We also consider the corresponding problem in the Client-Waiter version of the game.Publicationtype: Journal Article11 21