Discrete Lunch‎ > ‎

3rd Discrete Lunch: Graph Saturation Games

posted Aug 8, 2013, 7:56 AM by Dirk Oliver Theis   [ updated Aug 8, 2013, 8:01 AM ]
Mon June 17.
Ago talked about open question and results on graph saturation games.
A graph G is H-saturated if H is not a subgraph of G, but adding any edge to G causes H to be a subgraph. We can ask what is the minimum or maximum number of edges in an H-saturated graph on n vertices - they are known as the saturation number and extremal number, respectively. Something that is naturally between those values is the game saturation number: two players, prolonger and shortener, start with an empty graph on n vertices and they put down edges alternately, so that H is not a subgraph of the graph obtained during the game.  The game ends when the graph is H-saturated.  The game saturation number of H is the number of edges at the end of the game if prolonger's strategy is to have as many edges as possible at the end and shortener has the opposite strategy.