On saturation games

Dan Hefetz, Michael Krivelevich, Alon Naor, Miloš Stojaković

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

9 ציטוטים ‏(Scopus)

תקציר

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⊆Kn, 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.

שפה מקוריתאנגלית
עמודים (מ-עד)315-335
מספר עמודים21
כתב עתEuropean Journal of Combinatorics
כרך51
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2016
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On saturation games'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי