Maker Breaker on Digraphs

2020/03/30 by Frieze, Alan, Pegden, Wesley · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2003.13521

Abstract

We study two biassed Maker-Breaker games played on the complete digraph K_n. In the strong connectivity game, Maker wants to build a strongly connected subgraph. We determine the asymptotic optimal bias for this game viz. (n)/(log n). In the Hamiltonian game, Maker wants to build a Hamiltonian subgraph. We determine the asymptotic optimal bias for this game up to a constant factor.

Cited by

• The Maker-Breaker directed triangle game
• Some Maker-Breaker games on hypergraphs

Related

• Asymptotically Optimal Threshold Bias for the (a : b) Maker-Breaker Minimum Degree, Connectivity and Hamiltonicity Games
• Doubly biased Maker-Breaker Connectivity game
• Some Maker-Breaker games on hypergraphs
• Sharp thresholds for half-random games II
• Structure-biased Maker-Breaker Games