Survival time of a random graph
type: Item
instance of: scholarly article
title: Survival time of a random graph
zbMATH Open document ID: 0707.05054
DOI: 10.1007/BF02124675
published in: Combinatorica
publication date: 1989-01-01T00:00:00Z
review text: Edges are entered one by one in random order among n vertices. The hitting time \(\tau\) is the number of edges that have to be entered to realize a certain graph property \(\Pi\). The survival time \(\tau '\) is the number of edges, taken in the order of entrance, that have to be removed to violate property \(\Pi\). The main result is that \(\tau '/n\) has a negative exponential asymptotic distribution with mean 1/2 if \(\Pi\) is the property of k-connectivity.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60G40
zbMATH DE Number: 4160787
zbMATH Keywords: k-connectivity
zbMATH Keywords: random graph
zbMATH Keywords: optimal stopping times
author: Alan Frieze
MaRDI profile type: Publication
Wikidata QID: Q57401612
cites work: Q3344024
cites work: Q3715148
cites work: Q3267900
cites work: Q3286850
cites work: On the strength of connectedness of a random graph
description: scientific article; zbMATH DE number 4160787