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 ₜ_, with probability α1 > 0 we add a new vertex ᵤt_ and m random edges incident with ᵤt_. The neighbours of ut are chosen with probability proportional to degree. With probability α -α1 ≥ 0 we add ₘ_ random edges to existing vertices where the endpoints are chosen with probability proportional to degree. With probability 1-α-α0 we delete a random vertex, if there are vertices left to delete. With probability α0 we delete m random edges. Assuming that α + α1 + α0 > 1 and α0 is sufficently small, we show that for large ₖ, t_, the expected number of vertices of degree ₖ_ is approximately dkt_ where as ₖ_ → 8, dk_ ~ Ck_-1-β where and C_ > 0 is a constant. Note that _β_ can take any value greater than 1.