Component games on regular graphs
From MaRDI portal
Abstract: We study the (1:b) Maker-Breaker component game, played on the edge set of a d-regular graph. Maker's aim in this game is to build a large connected component, while Breaker's aim is to not let him do so. For all values of Breaker's bias b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players. To this end, we prove an extension of a theorem by Gallai-Hasse-Roy-Vitaver about graph orientations without long directed simple paths.
Recommendations
Cites work
- A Solution of the Shannon Switching Game
- Asymptotic random graph intuition for the biased connectivity game
- Biased Positional Games
- Biased positional games and the phase transition
- Chromatic number, girth and maximal degree
- Critical percolation on random regular graphs
- Expander graphs and their applications
- Global maker-breaker games on sparse graphs
- On the Edge-Expansion of Graphs
- Percolation on finite graphs and isoperimetric inequalities.
- Positional games on random graphs
- Ramanujan graphs
- Zur algebraischen Begründung der Graphentheorie. I
Cited in
(4)
This page was built for publication: Component games on regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5414147)
