C$${}_ 4$$-saturated graphs of minimum size.(English)Zbl 0719.05040

Let F be a given simple 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, define $$sat(n,F)=\min \{| E(G)|:| V(G)| =n,\;G$$ is F-saturated}, the minimum number of edges in an F- saturated graph on n vertices. 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, namely the extremal graphs, that are F-saturated. Denote $$C_ 4$$ the cycle on 4 vertices. In his earlier paper, the author proves that for $$n\geq 5$$, $$sat(n,C_ 4)=[(3n-5)/2],$$ moreover describes the extremal graphs; in this paper he gives a shorter argument.

MSC:

 05C35 Extremal problems in graph theory

Keywords:

F-saturated graph
Full Text: