$C_4$-saturated graphs of minimum size
Źsolt Tuza · Czech digital mathematics library · 1989
We consider simple undirected graphs, with bo loops or multiple edges.Standard terminology of graph theory is used; undefined notions can be found e.g. in [1].Let F be a given graph.Call a graph G F-saturated if F is not a subgraph of G, but a subgraph isomorphic to F appears whenever a new edge is added to G. Denoting by V(G) and E(G) the set of vertices and edges, respectively, of G, definethe minimum number of edges in an F-saturated graph on n vertices.Now the problem is to determine sat (n, F) for given F and n (possibly when n is large), and to describe the graphs G with n vertices and sat (n, F) edges, that are F-saturated.Note that for n < |V(F)| the complete graph is the unique F-saturated one.The first result of this type was published in 1964 (Erdos, Hajnal and Moon [2]), but it took two decades until the first general upper bound on sat (n, F) appeared (Kaszonyi and Tuza [3]).A survey of results is given in [5], where also hypergraphs and weakened conditions are discussed.It is surprising how difficult the determination of sat (n, F) is even in case of very small F. For instance, denoting by C k the cycle on k vertices, the value of sat (n, C 5 ) is not known.Perhaps it is 3n/2 + 0(1) as n tends to infinity.For C 4 , Oilman [4] proved the following result.