Survival time of a random graph |
| |
| Authors: | A M Frieze A M Frieze |
| |
| Institution: | 1. Department of Mathematics, Carnegie Mellon University, 15213, Pittsburgh, PA
|
| |
| Abstract: | LetV
n
={1, 2, ...,n} ande
1,e
2, ...,e
N
,N=
be a random permutation ofV
n
(2). LetE
t={e
1,e
2, ...,e
t} andG
t=(V
n
,E
t
). If is a monotone graph property then the hitting time () for is defined by=()=min {t:G
t
 }. Suppose now thatG
starts to deteriorate i.e. loses edges in order ofage, e
1,e
2, .... We introduce the idea of thesurvival time = () defined by t = max {u:(V
n, {e
u,e
u+1, ...,e
T
}) }. We study in particular the case where isk-connectivity. We show that
|
|
