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.
Comments