Name
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 (root 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 = Theta (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 Delta = 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). (c) 2015 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/rsa.20619 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
Games,Random Graphs | Discrete mathematics,Random regular graph,Combinatorics,Random graph,Vertex (geometry),struct,Degree (graph theory),Spanning tree,Longest path problem,Mathematics,Pancyclic graph | Journal |
Volume | Issue | ISSN |
47.0 | 4.0 | 1042-9832 |
Citations | PageRank | References |
1 | 0.39 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Asaf Ferber | 1 | 75 | 15.80 |
| michael krivelevich | 2 | 1688 | 179.90 |
| Humberto Naves | 3 | 24 | 4.08 |