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.


05C35 Extremal problems in graph theory
Full Text: EuDML