The Game Saturation Number of a Graph |
| |
| Authors: | James M. Carraher William B. Kinnersley Benjamin Reiniger Douglas B. West |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS AND STATISTICS, UNIVERSITY OF NEBRASKA, KEARNEY, NEBRASKAContract grant sponsor: NSF;2. Contract grant number: DMS 09‐14815.;3. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF RHODE ISLAND, KINGSTON, RHODE ISLAND;4. MATHEMATICS DEPARTMENT, RYERSON UNIVERSITY, TORONTO ONTARIO, CANADA;5. MATHEMATICS DEPARTMENT, ZHEJIANG NORMAL UNIVERSITY, JINHUA, ZHEJIANG, CHINA AND, MATHEMATICS DEPARTMENT, UNIVERSITY OF ILLINOIS, URBANA, ILLINOISContract grant sponsor: Recruitment Program of Foreign Experts, 1000 Talent Plan, State Administration of Foreign Experts Affairs, China. |
| |
| Abstract: | Given a family  and a host graph H, a graph  is  ‐saturated relative to H if no subgraph of G lies in  but adding any edge from  to G creates such a subgraph. In the  ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in  , until G becomes  ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively;  denotes the length under optimal play (when Max starts). Let  denote the family of odd cycles and  the family of n‐vertex trees, and write F for  when  . Our results include  ,  for  ,  for  , and  for  . We also determine  ; with  , it is n when n is even, m when n is odd and m is even, and  when  is odd. Finally, we prove the lower bound  . The results are very similar when Min plays first, except for the P4‐saturation game on  . |
| |
| Keywords: | saturation number graph game forbidden subgraph spanning tree |
|
|
and a host graph H, a graph 
is 
‐saturated relative to H if no subgraph of G lies in 
but adding any edge from 
to G creates such a subgraph. In the 
‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in 
, until G becomes 
‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; 
denotes the length under optimal play (when Max starts). Let 
denote the family of odd cycles and 
the family of n‐vertex trees, and write F for 
when 
. Our results include 
, 
for 
, 
for 
, and 
for 
. We also determine 
; with 
, it is n when n is even, m when n is odd and m is even, and 
when 
is odd. Finally, we prove the lower bound 
. The results are very similar when Min plays first, except for the P4‐saturation game on 
.