ИСТИНА

For a fixed graph F, the minimum number of edges in an edge-maximal F-free subgraph of G is called the F-saturation number. The asymptotics of the F-saturation number of the Erd¨os–R´enyi random graph G(n, p) for constant p ∈ (0, 1) was established for any complete graph and any star graph. We obtain the asymptotics of the C_m saturation number of G(n, p) for m > 5. Also we prove non-trivial linear (in n) lower bounds and upper bounds for the C4-saturation number of G(n, p) for some fixed values of p.