pith. sign in

arxiv: 1510.05852 · v1 · pith:YHIR2BFBnew · submitted 2015-10-20 · 🧮 math.CO

On the connectivity Waiter-Client game

classification 🧮 math.CO
keywords clientgraphwaitergamebeenbuildcaseconnected
0
0 comments X
read the original abstract

In this short note we consider a variation of the connectivity Waiter-Client game $WC(n,q,\mathcal{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 \frac{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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.