2023/06/17 by Kalinichenko, Olga, Miralaei, Meysam, Mohammadian, Ali +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.10375
For two given graphs G and F, a graph H is said to be weakly (G, F) -saturated if H is a spanning subgraph of G which has no copy of F as a subgraph and one can add all edges in E(G)∖ E(H) to H in some order so that a new copy of F is created at each step. The weak saturation number wsat(G, F) is the minimum number of edges of a weakly (G, F)-saturated graph. In this paper, we deal with the relation between wsat(G(n,p), F) and wsat(Kn, F), where G(n,p) denotes the Erdős--Rényi random graph and Kn denotes the complete graph on n vertices. For every graph F and constant p, we prove that wsat( G(n,p),F)= wsat(Kn,F)(1+o(1)) with high probability. Also, for some graphs F including complete graphs, complete bipartite graphs, and connected graphs with minimum degree 1 or 2, it is shown that there exists an ε(F)>0 such that, for any p\geqslant n-ε(F)log n, wsat( G(n,p),F)= wsat(Kn,F) with high probability.