Tight concentration of star saturation number in random graphs

DOI10.1016/J.DISC.2023.113572zbMath1518.05169arXiv2212.06101OpenAlexW4382361638MaRDI QIDQ6172308

No author found.

Publication date: 19 July 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: For given graphs $F$ and $G$, the minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$ is called the $F$-saturation number and denoted $mathrmsat(G,F)$. For the star $F=K_{1,r}$, the asymptotics of $mathrmsat(G(n,p),F)$ is known. We prove a sharper result: whp $mathrmsat(G(n,p),K_{1,r})$ is concentrated in a set of 2 consecutive points.

Full work available at URL: https://arxiv.org/abs/2212.06101

zbMATH Keywords

random graphssaturation numberstar graphs2 point concentration

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Small maximal matchings in random graphs.
• Star saturation number of random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given number of edges
• Saturated graphs with minimal number of edges
• On colouring random graphs
• On Pósa's Conjecture for Random Graphs
• The threshold for the square of a Hamilton cycle
• A Problem in Graph Theory
• Saturation in random graphs

Related Items (1)

On the Maximum Induced Density of Directed Stars and Related Problems

This page was built for publication: Tight concentration of star saturation number in random graphs