Random Deletion in a Scale-Free Random Graph Process

We study a dynamically evolving random graph which adds vertices and edges using preferential attachment and deletes vertices randomly. At time _t_, with probability α₁ > 0 we add a new vertex _ut_ and m random edges incident with _ut_. The neighbours of ut are chosen with probability proportional to degree. With probability α -α₁ ≥ 0 we add _m_ random edges to existing vertices where the endpoints are chosen with probability proportional to degree. With probability 1-α-α₀ we delete a random vertex, if there are vertices left to delete. With probability α₀ we delete m random edges. Assuming that α + α₁ + α₀ > 1 and α₀ is sufficently small, we show that for large _k, t_, the expected number of vertices of degree _k_ is approximately _dkt_ where as _k_ → 8, _dk_ ~ _Ck_-1-β where and _C_ > 0 is a constant. Note that _β_ can take any value greater than 1.