Fast embedding of spanning trees in biased maker-breaker games

DOI10.1016/j.ejc.2012.01.007zbMath1242.05179OpenAlexW2088725657MaRDI QIDQ427795

Asaf Ferber, Michael Krivelevich, Dan Hefetz

Publication date: 18 June 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2012.01.007

zbMATH Keywords

complete graphwinning strategyedge setMaker-Baker, tree embedding game

Mathematics Subject Classification ID

Trees (05C05) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (6)

Fast Strategies In Maker–Breaker Games Played on Random Boards ⋮ Generating random graphs in biased Maker-Breaker games ⋮ Building Spanning Trees Quickly in Maker-Breaker Games ⋮ Fast strategies in Waiter-Client games ⋮ Weak and strong \(k\)-connectivity games ⋮ Waiter-client triangle-factor game on the edges of the complete graph

Cites Work

• Unnamed Item
• Hamilton cycles in highly connected and expanding graphs
• Embedding nearly-spanning bounded degree trees
• On two problems regarding the Hamiltonian cycle game
• Expanding graphs contain all small trees
• A solution to the Box Game
• Fast winning strategies in maker-breaker games
• Tree embeddings
• Embedding Spanning Trees in Random Graphs
• Asymptotic random graph intuition for the biased connectivity game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Sharp threshold for the appearance of certain spanning trees in random graphs
• Remarks on positional games. I
• Biased Positional Games
• On Biased Positional Games
• Deterministic Graph Games and a Probabilistic Intuition
• Expanders Are Universal for the Class of All Spanning Trees
• Combinatorial Games

This page was built for publication: Fast embedding of spanning trees in biased maker-breaker games