On K₄-saturated Graphs
by
Kinnari Amin
Emory University
Coauthors: Jill Faudree and Ronald Gould

Let H be a graph. Let G be a graph on n vertices. Any H-free graph G is called H-saturated if the addition of any edge e ∉ E(G) results in H as a subgraph of G. The minimum size of an H-saturated graph on n vertices is denoted by sat(n, H). The edge spectrum for the family of graphs with property P is the set of all sizes of graphs with property P. In this talk, I will present new results about K₄-saturated graphs. First we show that if a graph G is K₄-saturated, then diam(G) = 2 and G is at least 2-connected. We show that if G is a K₄-saturated graph, then either G ≅ K_{1, 1, n-2} or d(G) ≥ 3. We also show exact structure of K₄-saturated graph with k(G)=2 and k(G)=3. Finally, I will present the main result that there is a K₄-saturated graph G of order n if and only if either G is complete tripartite or 3n -8 ≤ |E(G)| ≤ [(n² - n + 4)/3].

Date received: March 24, 2009