What question did this study set out to answer?

The aim is to explore the weak saturation number for graphs, particularly in relation to random graphs and complete graphs.

February 22, 2026

Weak Saturation Numbers in Random Graphs

Puntos clave

The aim is to explore the weak saturation number for graphs, particularly in relation to random graphs and complete graphs.
Analyze the definition of weakly saturated graphs.
Investigate the relationship between Erdős–Rényi random graphs and complete graphs.
Prove probabilistic results concerning the existence of weak saturation numbers for various graph classes.
Establish that weak saturation numbers show high probability behavior in random graphs.
Identify conditions under which weak saturation numbers can exist in certain graph types like complete and bipartite graphs.
Demonstrate a link between specific graph properties and their weak saturation numbers with high certainty.

Resumen

ABSTRACT For two given graphs and , a graph is said to be weakly ‐saturated if is a spanning subgraph of which has no copy of as a subgraph and one can add all edges in to in some order so that a new copy of is created at each step. The weak saturation number is the minimum number of edges of a weakly ‐saturated graph. In this paper, we deal with the relation between and , where denotes the Erdős–Rényi random graph and denotes the complete graph on vertices. For any graph and constant , we prove that with high probability. Also, for some graphs , including complete graphs, complete bipartite graphs, and connected graphs with minimum degree or , it is shown that there exists an such that, for every with high probability.

Me gusta

Guardar