Saturation numbers of bipartite graphs in random graphs

MaRDI QIDQ6433237zbMATH OpenFDO

Authors Meysam Miralaei, A. Mohammadian, B. Tayfeh-Rezaie, M. E. Zhukovskii

Publication date 16 April 2023

Abstract: For a given graph $F$, the $F$-saturation number of a graph $G$, denoted by $sat(G,F)$, is the minimum number of edges in an edge-maximal $F$-free subgraph of $G$. In 2017, Kor'andi and Sudakov determined $sat(G(n,p),K_r)$ asymptotically, where $G(n,p)$ denotes the ErdH{o}s-R'enyi random graph and $K_r$ is the complete graph on $r$ vertices. In this paper, among other results, we present an asymptotic upper bound on $sat(G(n,p),F)$ for any bipartite graph $F$ and also an asymptotic lower bound on $sat(G(n,p),F)$ for any complete bipartite graph $F$.

This page was built for publication: Saturation numbers of bipartite graphs in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433237)