The Game Saturation Number of a Graph

Given a family F and a host graph H, a graph G ⊆ H is F-saturated relative to H if no subgraph of G lies in F but adding any edge from E(H) - E(G) to G creates such a subgraph. In the F-saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in F, until G becomes F-saturated relative to H. They aim to maximize or minimize the length of the game, respectively; satg(F;H) denotes the length under optimal play (when Max starts). Let O denote the family of odd cycles and the family of n-vertex trees, and write F for when F = {F}. Our results include satg(O; Kn) = [n/2] [n/2], satg(Tn; Kn) = (n-2/2) + 1 for n ≥ 6, satg(K1,3; Kn) = 2[Tn/2] for n ≥ 8, and satg(P4; Kn) ∈ {[4n/f] , [4n/5]} for n ≥ 5. We also determine satg(P4; Km;n); with m ≥ n, it is n when n is even, m when n is odd and m is even, and m + [n/2] when mn is odd. Finally, we prove the lower bound satg(C4; Kn,n) ≥ 1/21n13/12 – O(n35/36). The results are very similar when Min plays first, except for the P4-saturation game on Km,n.