Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/15976
Title: | Global Maker-Breaker games on sparse graphs | Authors: | Hefetz D. Krivelevich M. Stojaković, Miloš Szabó T. |
Issue Date: | 1-Feb-2011 | Journal: | European Journal of Combinatorics | Abstract: | In this paper we consider Maker-Breaker games, played on the edges of sparse graphs. For a given graph property P we seek a graph (board of the game) with the smallest number of edges on which Maker can build a subgraph that satisfies P. In this paper we focus on global properties. We prove the following results: (1) for the positive minimum degree game, there is a winning board with n vertices and about 10n/7 edges, on the other hand, at least 11n/8 edges are required; (2) for the spanning k-connectivity game, there is a winning board with n vertices and (1+ok(1))kn edges; (3) for the Hamiltonicity game, there is a winning board of constant average degree; (4) for a tree T on n vertices of bounded maximum degree δ, there is a graph G on n vertices and at most f(δ).n edges, on which Maker can construct a copy of T. We also discuss biased versions of these games and argue that the picture changes quite drastically there. © 2010 Elsevier Ltd. | URI: | https://open.uns.ac.rs/handle/123456789/15976 | ISSN: | 01956698 | DOI: | 10.1016/j.ejc.2010.09.005 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
11
checked on Sep 9, 2023
Page view(s)
11
Last Week
11
11
Last month
0
0
checked on May 3, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.