Cycle Saturation in Random Graphs

Yury Demidovich; Maksim Zhukovskii

doi:10.1007/978-3-030-83823-2_129

Cycle Saturation in Random Graphs

Yury Demidovich^*, Maksim Zhukovskii

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

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 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 C₄ -saturation number of G(n, p) for some fixed values of p.

Original language	English (US)
Title of host publication	Trends in Mathematics
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	811-816
Number of pages	6
DOIs	https://doi.org/10.1007/978-3-030-83823-2_129
State	Published - 2021

Publication series

Name	Trends in Mathematics
Volume	14
ISSN (Print)	2297-0215
ISSN (Electronic)	2297-024X

Bibliographical note

Funding Information:
Acknowledgements. This work was carried out with the financial support of the Ministry of Education and Science of the Russian Federation, in the framework of Megagrant no. 075-15-2019-1926. The work of the first author was also supported by the Simons Foundation.

Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Cycle
Extremal graph theory
Random graph
Saturation

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1007/978-3-030-83823-2_129

Cite this

@inbook{fa92de54c95049a3960c2006790ae378,

title = "Cycle Saturation in Random Graphs",

abstract = "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{\"o}s–R{\'e}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.",

keywords = "Cycle, Extremal graph theory, Random graph, Saturation",

author = "Yury Demidovich and Maksim Zhukovskii",

note = "Funding Information: Acknowledgements. This work was carried out with the financial support of the Ministry of Education and Science of the Russian Federation, in the framework of Megagrant no. 075-15-2019-1926. The work of the first author was also supported by the Simons Foundation. Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2021",

doi = "10.1007/978-3-030-83823-2_129",

language = "English (US)",

series = "Trends in Mathematics",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "811--816",

booktitle = "Trends in Mathematics",

address = "Germany",

}

TY - CHAP

T1 - Cycle Saturation in Random Graphs

AU - Demidovich, Yury

AU - Zhukovskii, Maksim

N1 - Funding Information: Acknowledgements. This work was carried out with the financial support of the Ministry of Education and Science of the Russian Federation, in the framework of Megagrant no. 075-15-2019-1926. The work of the first author was also supported by the Simons Foundation. Publisher Copyright: © 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - Cycle

KW - Extremal graph theory

KW - Random graph

KW - Saturation

UR - http://www.scopus.com/inward/record.url?scp=85114107440&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-83823-2_129

DO - 10.1007/978-3-030-83823-2_129

M3 - Chapter

AN - SCOPUS:85114107440

T3 - Trends in Mathematics

SP - 811

EP - 816

BT - Trends in Mathematics

PB - Springer Science and Business Media Deutschland GmbH

ER -

Cycle Saturation in Random Graphs

Abstract

Publication series

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this