Originator(s): L. Kásonyi and Zs. Tuza (presented by Paul Wenger - REGS 2009)
Definitions: Given a graph H, a graph G is H-saturated if G does not contain H but the addition of an edge joining any pair of nonadjacent vertices of G completes a copy of H. The saturation number of H, written sat(n,H) is the minimum number of edges in an H-saturated graph with n vertices (assuming n≥|V(H)|).
Background: Erdős, Hajnal, and Moon [EHM] proved the first result about saturation numbers: sat(n,Kt) = (t-2)[n-½(t-1)]. The later paper by Kásonyi and Tuza [KT] initiated a systematic study. They showed that sat(n,G)<sat(n,Kt) when G has t vertices and differs from Kt. We present their general upper bound in terms of vertex covering. Let β(H) denote the minimum number of vertices in a set containing at least one endpoint of every edge in H; such a set is a vertex cover of H.
Theorem: [KT]
For a graph H, always sat(n,H) ≤ (b+(u-1)/2)n - b(b+u)/2,
where b=β(H)-1 and u is the least value of
Δ(H-S) for sets S of size b contained in a smallest
vertex cover of H.
Proof:
Let G0=Kb∨ (n-b)K1. Let S
being the set of vertices having degree n-1 and T be the
independent set of size n-b. Since β(H)=b+1 and S is
a vertex cover in G0, there is no copy of H in
G0. Obtain G1 from G0 by
adding edges with both endpoints in T so that every vertex of T
has fewer than u neighbors in T, but adding any further edge will
destroy that property. Adding any edge to G1 creates a graph
containing H, since a vertex of T given u neighbors in
T can serve as the last vertex in a vertex cover for a copy of H
(since H ⊆ Kb∨ (|V(H)|-b)K1). Therefore,
contained in G1 and containing G0 is some
H-saturated graph G. Since G has no more edges than
G1, the degree-sum formula yields
sat(n,H) ≤ ½[b(n-1)+(n-b)(b+u-1)], which simplifies to the
formula claimed. ♦
The bound is sharp for complete graphs, reducing to the Erdős-Moon formula. For sparse graphs, this bound is not very good, since sparse graphs have large vertex cover numbers but small saturation numbers. For the k-vertex path, for example, Kásonyi-Tuza [KT] showed that sat(n,Pk)<n when n is sufficiently large relative to k (there is a Pk-saturated forest). It is easy to see that sat(n,P4) is n/2 when n is even and (n+3)/2 when n is odd [KT].
Problem 1: (R. Faudree; see [FFGJ]) Characterize all trees T such that sat(n,T)<n.
Comments: Faudree, Faudree, Gould, and Jacobson [FFGJ] proved that if a tree T has a leaf whose distance to the nearest vertex of degree at least 3 exceeds the radius, then sat(n,T)<n. The tree with k vertices whose saturation number is smallest is formed by subdividing one edge of a star; is saturation number is n-⌊(n+k-2)/k⌋ [FFGJ]. However, the k-vertex tree with the largest saturation number is the star itself: sat(n,K1,k-1) = (k-2)n/2-⌊(k-1)²/4⌋/2 [KT]. The famous Erdős-Sós Conjecture states that if an n-vertex graph has more than (k-1)n/2 edges, then it contains all trees with k edges.
Problem 2: (Gould) Compute sat(n,Ck), where Ck denotes the cycle with k vertices.
Comments: Ollmann [O] proved that sat(n,C4) = (3n-5)/2, and Chen [C] proved sat(n,C5) is within 1 of 10(n-1)/7 when n≥11. Barefoot et al. [BCEPST] showed that there are constants c1 and c2 such that sat(n,Cm) lies between n+c1n/m and n+c2n/m. The best known upper bound for c2 is due to Łuczak, Gould, and Schmitt [LGS] for most m and n; they showed that sat(n,Cm)≤(1+2/(m-&epsilon))n+5m²/4, where m≥10, ε=2, n≥3m if m is even, and m≥17, ε=3, n≥7m if m is odd. Also, sat(n,Cn)=⌊(3n+1)/2⌋ when n≥20 [CES].
Question 3: For a fixed n and a fixed graph H, determine all possible sizes (numbers of edges) for H-saturated graphs on n vertices.
Comments: The maximum number of edges in an H-saturated graph with n vertices is the well-studied Turán number ex(n,H). Barefoot et al. [BCEPST] showed for n≥5 that there exist K3-saturated graphs on n vertices with m edges for 2n-5 ≤ m ≤ ⌊(n-1)^2/4⌋+1. Amin, J. Faudree, and Gould [AFG] determined that if G is a K4-saturated graph on n vertices, then G is a complete tripartite graph or 3n-8 ≤ |E(G)| ≤ (n2-n+4)/3.
Problem 4: Compute saturation numbers for other graphs.
Comments: Kásonyi and Tuza [KT] considered matchings: sat(n,tK2)=3t-3 when n≥3t-3. Gould (et al.?) determined sat(n,tKp), a common generalization of the [EHM] result for complete graphs and the [KT] result for matchings. The value is (p-2)(n-p+2)+(t-1)(p+1)p/2+(p-t)(p-t-1)/2. Chen, Gould, and Faudree [CGF] computed sat(n,Bp), where Bp consists of p triangles with a common edge (a "book"). When n≥p³+p, the value is ½[(p+1)(n-1)-⌊p²/4⌋+&epsilon], where ε is 1 if p≡n-p/2≡0 mod 2 and 0 otherwise. They also generalized this to the graph consisting of p copies of Kb+1 sharing a common b-clique. Finally, There are generalizations to hypergraphs [B1,P] and analogues for bipartite graphs [B2,W].
References:
[AFG] Amin, K; Faudree, J.; Gould, R.; Saturation numbers for
K4-free graphs, in preparation.
[BCEPST] Barefoot, C. A.; Clark, L. H.; Entringer, R. C.; Porter, T. D.;
Székely, L. A.; Tuza, Zs. Cycle-saturated graphs of minimum size.
Selected papers in honour of Paul Erdős on the occasion of his 80th
birthday (Keszthely, 1993). Discrete Math. 150 (1996), no. 1-3, 31-48.
[B1] Bollobás, B.
On generalized graphs.
Acta Math. Acad. Sci. Hungar 16 1965 447-452.
[B2] Bollobás, B. On a conjecture of Erdős, Hajnal and Moon.
Amer. Math. Monthly 74 1967 178-179.
[CES] Clark, L.H., Entringer, R.C., Shapiro, H.D., Smallest maximally
nonhamiltonian graphs II, Graphs Combin. 8 (1992) 225-231.
[CFG] Chen, Guantao; Faudree, Ralph J.; Gould, Ronald J. Saturation numbers of
books. Electron. J. Combin. 15 (2008), no. 1, Research Paper 118, 12 pp.
[EHM] Erdős, P.; Hajnal, A.; Moon, J. W. A problem in graph theory. Amer.
Math. Monthly 71 1964 1107-1110.
[FFGJ] Faudree, J.R.; Faudree, R.J.; Gould, R.J; Jacobson, M.S;
Saturation numbers for trees, in preparation.
[GLS] Gould, Ronald; Łuczak, Tomasz; Schmitt, John; Constructive upper
bounds for cycle-saturated graphs of minimum size. Electron. J. Combin. 13
(2006), no. 1, Research Paper 29, 19 pp. (electronic).
[KT] Kászonyi, L.; Tuza, Zs. Saturated graphs with minimal number of
edges. J. Graph Theory 10 (1986), no. 2, 203-210.
[O] Ollmann, L. T.
K2,2-saturated graphs with a minimal number of edges.
Proceedings of the Third Southeastern Conference on Combinatorics, Graph
Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1972), pp.
367-392. Florida Atlantic Univ., Boca Raton, Fla., 1972.
[P]
Pikhurko, Oleg;
Results and open problems on minimum saturated hypergraphs.
Ars Combin. 72 (2004), 111-127.
[W] Wessel, W.
Über eine Klasse paarer Graphen. I. Beweis einer Vermutung von Erdős,
Hajnal und Moon.
Wiss. Z. Techn. Hochsch. Ilmenau 12 1966 253-256.