Saturation Numbers in Tripartite Graphs. Issue 4 (28th March 2016)

• Record Type: Journal Article
• Authors: Sullivan, Eric; Wenger, Paul S.
• Is Part Of: Journal of graph theory. Volume 84:Issue 4(2017)
• Page Start: 428
• Page End: 442
• Publication Date: 2016-03-28
• Subjects: saturation -- tripartite -- subgraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22033
• Languages: English
• ISSNs: 0364-9024

Abstract

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 .