Cycle Saturation in Random Graphs

Yury Demidovich*, Maksim Zhukovskii

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


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ös–Rényi 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 Cm -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.

Original languageEnglish (US)
Title of host publicationTrends in Mathematics
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages6
StatePublished - 2021

Publication series

NameTrends in Mathematics
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X


  • Cycle
  • Extremal graph theory
  • Random graph
  • Saturation

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Cycle Saturation in Random Graphs'. Together they form a unique fingerprint.

Cite this