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

Discrete Lunch >