2015/10/20 by Sylwia Antoniuk, Antoniuk, Sylwia, Codruut Grosu +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Mathematics · #05C40 #05C57 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Economic theories and models #FOS: Mathematics #Game Theory and Applications #math.CO #msc:05C40 #msc:05C57
paper · pdf · doi:10.48550/arxiv.1510.05852
arxiv created 2015/10/20 · openalex publication_date 2015/10/20 · arxiv updated 2015/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this short note we consider a variation of the connectivity Waiter-Client game WC(n,q,A) played on an n-vertex graph G which consists of q+1 disjoint spanning trees. In this game in each round Waiter offers Client q+1 edges of G which have not yet been offered. Client chooses one edge and the remaining q edges are discarded. The aim of Waiter is to force Client to build a connected graph. If this happens Waiter wins. Otherwise Client is the winner. We consider the case where 2 < q+1 < \lfloor (n-1)/(2)\rfloor and show that for each such q there exists a graph G for which Client has a winning strategy. This result stands in opposition to the case where G consists of just 2 spanning trees or where G is a complete graph, since it has been shown that for such graphs Waiter can always force Client to build a connected graph.