Saturation Numbers in Tripartite Graphs |
| |
| Authors: | Eric Sullivan Paul S. Wenger |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICAL AND STATISTICAL SCIENCES, UNIVERSITY OF COLORADO DENVER, Denver, CO;2. SCHOOL OF MATHEMATICAL SCIENCES, ROCHESTER INSTITUTE OF TECHNOLOGY, ROCHESTER, NY |
| |
| Abstract: | Given graphs H and F, a subgraph  is an F‐saturated subgraph of H if  , but  for all  . The saturation number of F in H, denoted  , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For  and n1, n2, and n3 sufficiently large, we determine  and  exactly and  within an additive constant. We also include general constructions of  ‐saturated subgraphs of  with few edges for  . |
| |
| Keywords: | saturation tripartite subgraph |
|
|
is an F‐saturated subgraph of H if 
, but 
for all 
. The saturation number of F in H, denoted 
, is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For 
and n1, n2, and n3 sufficiently large, we determine 
and 
exactly and 
within an additive constant. We also include general constructions of 
‐saturated subgraphs of 
with few edges for 
.