On saturation games

DOI10.1016/J.EJC.2015.05.017zbMATH Open1321.05158arXiv1406.2111OpenAlexW1658226621MaRDI QIDQ499485FDOQ499485

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)

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.

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

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

zbMATH Keywords

saturation number

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Saturated graphs with minimal number of edges
• Title not available (Why is that?)
• A survey of minimum saturated graphs
• A Problem in Graph Theory
• Game matching number of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arc coverings of graphs
• Game saturation of intersecting families
• 1-Faktoren von Graphen. (1-factors of graphs)
• The Game Saturation Number of a Graph
• An upper bound on the extremal version of Hajnal's triangle-free game

Cited In (13)

• The constructor-blocker game
• Games of crowding
• The game of \(\mathcal F\)-saturator
• Game saturation of intersecting families
• Excess games
• Linear bounds for cycle-free saturation games
• Graph 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)