Premium
Generating random graphs in biased Maker‐Breaker games
Author(s) -
Ferber Asaf,
Krivelevich Michael,
Naves Humberto
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20619
Subject(s) - combinatorics , path (computing) , graph , random graph , mathematics , discrete mathematics , degree (music) , decision maker , tree (set theory) , longest path problem , computer science , shortest path problem , operations research , physics , programming language , acoustics
Abstract We present a general approach connecting biased Maker‐Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker‐Breaker games. In particular, we show that for b = o ( n ) , Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a ( 1 : b ) game on E ( K n ) . As another application, we show that for b = Θ ( n / ln n ) , playing a ( 1 : b ) game on E ( K n ) , Maker can build a graph which contains copies of all spanning trees having maximum degree Δ = O ( 1 ) with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T ). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 615–634, 2015