
Open access
Date
2019-05-17Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
In this note we establish a resilience version of the classical hitting time result of Bollobás and Thomason regarding connectivity. A graph G is said to be α-resilient with respect to a monotone increasing graph property P if for every spanning subgraph H⊆G satisfying degH(v)⩽αdegG(v) for all v∈V(G), the graph G−H still possesses P. Let {Gi} be the random graph process, that is a process where, starting with an empty graph on n vertices G0, in each step i⩾1 an edge e is chosen uniformly at random among the missing ones and added to the graph Gi−1. We show that the random graph process is almost surely such that starting from m⩾(16+o(1))nlogn, the largest connected component of Gm is (12−o(1))-resilient with respect to connectivity. The result is optimal in the sense that the constants 1/6 in the number of edges and 1/2 in the resilience cannot be improved upon. We obtain similar results for k-connectivity. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000345303Publication status
publishedExternal links
Search via swisscovery
Journal / series
The Electronic Journal of CombinatoricsVolume
Pages / Article No.
Publisher
Electronic Journal of CombinatoricsOrganisational unit
03672 - Steger, Angelika / Steger, Angelika
Funding
169242 - Saturation Games and Robust Random Structures (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics