The Game Saturation Number of a Graph. Issue 2 (16th September 2016)

• Record Type: Journal Article
• Authors: Carraher, James M.; Kinnersley, William B.; Reiniger, Benjamin; West, Douglas B.
• Is Part Of: Journal of graph theory. Volume 85:Issue 2(2017)
• Page Start: 481
• Page End: 495
• Publication Date: 2016-09-16
• Subjects: saturation number -- graph game -- forbidden subgraph -- spanning tree; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22074
• Languages: English
• ISSNs: 0364-9024

Abstract

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 .