Building spanning trees quickly in maker-breaker games

DOI10.1137/140976054zbMATH Open1331.91048arXiv1304.4108OpenAlexW1656969381MaRDI QIDQ2947437FDOQ2947437

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)

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.

Full work available at URL: https://arxiv.org/abs/1304.4108

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

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)

Cites Work

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

Cited In (12)

• 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
• 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)