Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/5898
Title: | On saturation games | Authors: | Hefetz D. Krivelevich M. Naor A. Stojaković, Mila |
Issue Date: | 1-Jan-2016 | Journal: | European Journal of Combinatorics | Abstract: | © 2015 Elsevier Ltd. A graph G =(V, E) is said to be saturated with respect to a monotone increasing graph property P, if G∉P but G∪{e}∈P for every e∈(V2)\E. The saturation game (n,P) is played as follows. Two players, called Mini and Max, progressively build a graph G⊆K<inf>n</inf>, which does not satisfy P. Starting with the empty graph on n vertices, the two players take turns adding edges e∈(V(Kn)2)\E(G), for which G∪{e}∉P, until no such edge exists (i.e.until G becomes P-saturated), at which point the game is over. Max's goal is to maximize the length of the game, whereas Mini aims to minimize it. The score of the game, denoted by s(n,P), is the number of edges in G at the end of the game, assuming both players follow their optimal strategies.We prove lower and upper bounds on the score of games in which the property the players need to avoid is being k-connected, having chromatic number at least k, and admitting a matching of a given size. In doing so we demonstrate that the score of certain games can be as large as the Turán number or as low as the saturation number of the respective graph property, and also that the score might strongly depend on the identity of the first player to move. | URI: | https://open.uns.ac.rs/handle/123456789/5898 | ISSN: | 01956698 | DOI: | 10.1016/j.ejc.2015.05.017 |
Appears in Collections: | FTN Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
6
checked on May 10, 2024
Page view(s)
10
Last Week
9
9
Last month
0
0
checked on May 10, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.