The Game Saturation Number of a Graph. Issue 2 (16th September 2016) - Carraher, James M.; Kinnersley, William B.; Reiniger, Benjamin; West, Douglas B.
Abstract: 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; sat g ( F ; H ) denotes the length under optimal play (when Max starts). Let O denote the family of odd cycles and T n the family of n ‐vertex trees, and write F for F when F = F . Our results include sat g ( O ; K n ) = ⌊ n 2 ⌋ ⌈ n 2 ⌉, sat g ( T n ; K n ) = ( n − 2 2 ) + 1 for n ≥ 6, sat g ( K 1, 3 ; K n ) = 2 ⌊ n 2 ⌋ for n ≥ 8, and sat g ( P 4 ; K n ) ∈ ⌊ 4 n 5 ⌋, ⌈ 4 n 5 ⌉ for n ≥ 5 . We also determine sat g ( P 4 ; K m, 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 m n is odd. Finally, we prove the lower bound sat g ( C 4 ; K n, n ) ≥ 1 21 n 13 / 12 − O ( n 35 / 36 ) . The results are very similar when Min plays first, except for the P 4 ‐saturation game on K m, n .