Building spanning trees quickly in maker-breaker games

DOI10.1137/140976054MaRDI QIDQ2947437zbMATH OpenOpenAlexFDO

Authors Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz, Anita Liebenau

Publication date 23 September 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.4108, http://hdl.handle.net/1721.1/100546

zbMATH Keywords

spanning treespositional gamesmaker-breaker games

Mathematics Subject Classification ID

Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Abstract: For a tree T on n vertices, we study the Maker-Breaker game, played on the edge set of the complete graph on n vertices, which Maker wins as soon as the graph she builds contains a copy of T. We prove that if T has bounded maximum degree, then Maker can win this game within n+1 moves. Moreover, we prove that Maker can build almost every tree on n vertices in n-1 moves and provide non-trivial examples of families of trees which Maker cannot build in n-1 moves.

Recommendations

• Building spanning trees quickly in maker-breaker games
• Fast embedding of spanning trees in biased maker-breaker games
• Fast embedding of spanning trees in biased maker-breaker games
• Fast winning strategies in maker-breaker games
• Global maker-breaker games on sparse graphs

Cites work

• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Winning Strategy for the Ramsey Graph Game
• Biased Positional Games
• Combinatorial Games
• Deterministic Graph Games and a Probabilistic Intuition
• Embedding spanning trees in random graphs
• Expanders Are Universal for the Class of All Spanning Trees
• Fast embedding of spanning trees in biased maker-breaker games
• Fast strategies in maker-breaker games played on random boards
• Fast winning strategies in maker-breaker games
• On Biased Positional Games
• On the clique-game
• On the maximum degree in a random tree
• On two problems regarding the Hamiltonian cycle game
• Positional games
• Proof of a Packing Conjecture of Bollobás
• Ramsey games
• The number of \(F\)-matchings in almost every tree is a zero residue
• Weak and strong \(k\)-connectivity games
• Winning strong games through fast strategies for weak games

Cited in

(13)

• Strong Ramsey games: drawing on an infinite board
• Spanning tree game as prim would have played
• On a base exchange game on bispanning graphs
• Spanning trees of dense directed graphs
• Fast embedding of spanning trees in biased maker-breaker games
• Maker-breaker domination number for Cartesian products of path graphs \(P_2\) and \(P_n\)
• Winning Fast in Sparse Graph Construction Games
• Bounds for the competition-independence game on trees
• Fast strategies in Waiter-Client games
• Fast embedding of spanning trees in biased maker-breaker games
• Generating random graphs in biased maker-breaker games
• Hamiltonian maker-breaker games on small graphs
• Efficient winning strategies in random-turn maker-breaker games

This page was built for publication: Building spanning trees quickly in maker-breaker games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947437)