Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке:
https://open.uns.ac.rs/handle/123456789/15976
Назив: | Global Maker-Breaker games on sparse graphs | Аутори: | Hefetz D. Krivelevich M. Stojaković, Miloš Szabó T. |
Датум издавања: | 1-феб-2011 | Часопис: | European Journal of Combinatorics | Сажетак: | 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 |
Налази се у колекцијама: | PMF Publikacije/Publications |
Приказати целокупан запис ставки
SCOPUSTM
Навођења
11
проверено 09.09.2023.
Преглед/и станица
11
Протекла недеља
11
11
Протекли месец
0
0
проверено 03.05.2024.
Google ScholarTM
Проверите
Алт метрика
Ставке на DSpace-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.