Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/15976
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hefetz D. | en_US |
dc.contributor.author | Krivelevich M. | en_US |
dc.contributor.author | Stojaković, Miloš | en_US |
dc.contributor.author | Szabó T. | en_US |
dc.date.accessioned | 2020-03-03T15:02:08Z | - |
dc.date.available | 2020-03-03T15:02:08Z | - |
dc.date.issued | 2011-02-01 | - |
dc.identifier.issn | 01956698 | en_US |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/15976 | - |
dc.description.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. | en |
dc.relation.ispartof | European Journal of Combinatorics | en |
dc.title | Global Maker-Breaker games on sparse graphs | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.doi | 10.1016/j.ejc.2010.09.005 | - |
dc.identifier.scopus | 2-s2.0-78049511319 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/78049511319 | - |
dc.description.version | Published | en_US |
dc.relation.lastpage | 177 | en |
dc.relation.firstpage | 162 | en |
dc.relation.issue | 2 | en |
dc.relation.volume | 32 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.orcid | 0000-0002-2545-8849 | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
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.