ISSN:
1439-6912
Keywords:
05 C 80
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract LetV n ={1, 2, ...,n} ande 1,e 2, ...,e N ,N= $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$$ 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 1) $$\mathop {\lim }\limits_{n \to \infty } \Pr (\tau ' \geqq an) = e^{ - 2a} {\mathbf{ }}for{\mathbf{ }}a \in R^ + $$ 2) $$\mathop {\lim }\limits_{n \to \infty } \frac{1}{n}E(\tau ') = \frac{1}{n}$$ i.e.τ′/n is asymptotically negative exponentially distributed with mean 1/2.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02124675
Permalink
