On saturation games

DOI10.1016/J.EJC.2015.05.017MaRDI QIDQ499485zbMATH OpenOpenAlexFDO

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

Publication date 30 September 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.2111

zbMATH Keywords

saturation number

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Abstract: A graph $G=(V,E)$ is said to be saturated with respect to a monotone increasing graph property $mathcalP$, if $GotinmathcalP$ but $GcupeinmathcalP$ for every $$. The saturation game $(n,mathcalP)$ is played as follows. Two players, called Mini and Max, progressively build a graph $Gsubseteq{K}_n$, which does not satisfy $mathcalP$. Starting with the empty graph on $n$ vertices, the two players take turns adding edges $$, for which $GcupeotinmathcalP$, until no such edge exists (i.e. until $G$ becomes $mathcalP$-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,mathcalP)$, 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'an number or as low as the saturation number of the respective graph property. We also demonstrate that the score might strongly depend on the identity of the first player to move.

Recommendations

• The Game Saturation Number of a Graph
• Graph saturation games
• Saturation games for odd cycles
• Linear bounds for cycle-free saturation games
• The game of \(\mathcal F\)-saturator

Cites work

• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3166040 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 140096 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• 1-Faktoren von Graphen. (1-factors of graphs)
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• An upper bound on the extremal version of Hajnal's triangle-free game
• Arc coverings of graphs
• Game matching number of graphs
• Game saturation of intersecting families
• Saturated graphs with minimal number of edges
• The Factorization of Linear Graphs
• The Game Saturation Number of a Graph

Cited in

(13)

• Games of crowding
• The game of \(\mathcal F\)-saturator
• The constructor-blocker game
• Game saturation of intersecting families
• Excess games
• Graph saturation games
• Linear bounds for cycle-free saturation games
• Saturation games for odd cycles
• The Game Saturation Number of a Graph
• The \(P_5\)-saturation game
• Flow games
• An upper bound on the extremal version of Hajnal's triangle-free game
• Spanning-tree games

This page was built for publication: On saturation games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q499485)