The paper is devoted to the spreading of one message within a random graph evolving by a Norros-Reittu preferential attachment model (PAM). The PAM was introduced in a pioneer paper by Norros and Reittu (2006). By PAM a network may grow by attachment of new edges between a new node and existing nodes proportionally to their capacities, i.e., their mean node degrees. The number of edges between two nodes follows a Poisson distribution whose mean is determined by the weights of the nodes. Evolution models with a random number of newly created edges are considered the most realistic for modeling real networks. The PAM plays a double role. It forms new edges between new and existing nodes and propagates the message from an existing node having it to a node without it. In our study, we modify the Norros-Reittu model by allowing us to delete one of the existing nodes at each step of the evolution. The statement of the problem is to find a minimum number of steps when the message is lost. The result depends on the choice of the initial graph from which the evolution starts.
