Saturation Numbers in Tripartite Graphs. Issue 4 (28th March 2016) - Sullivan, Eric; Wenger, Paul S.
Abstract: Given graphs H and F, a subgraph G ⊆ H is an F ‐ saturated subgraph of H if F ⊈ G, but F ⊆ G + e for all e ∈ E ( H ) ∖ E ( G ) . The saturation number of F in H, denoted sat ( H, F ), 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 ℓ ≥ 1 and n 1, n 2, and n 3 sufficiently large, we determine sat ( K n 1, n 2, n 3, K ℓ, ℓ, ℓ ) and sat ( K n 1, n 2, n 3, K ℓ, ℓ, ℓ − 1 ) exactly and sat ( K n 1, n 2, n 3, K ℓ, ℓ, ℓ − 2 ) within an additive constant. We also include general constructions of K ℓ, m, p ‐saturated subgraphs of K n 1, n 2, n 3 with few edges for ℓ ≥ m ≥ p > 0 .