Survival time of a random graph
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.
scientific article; zbMATH DE number 4160787
scientific article