On the robustness of random -cores

The k -core of a graph is its maximal subgraph with minimum degree at least  k . In this paper, we address robustness questions about k -cores (with fixed k ≥ 3 ). Given a k -core, remove one edge uniformly at random and find its new k -core. We are interested in how many vertices are deleted from the original k -core to find the new one. This can be seen as a measure of robustness of the original k -core. We prove that, if the initial k -core is chosen uniformly at random from the k -cores with n vertices and m edges, its robustness depends essentially on its average degree  c . We prove that, if c → k , then the new k -core is empty with probability 1 − o ( 1 ) . We define a constant c k ′ such that when k + ε < c < c k ′ − ε , the new k -core is empty with probability bounded away from zero and, if c > c k ′ + ψ ( n ) with ψ ( n ) = ω ( n − 1 / 2 log n ) , ψ ( n ) > 0 and c is bounded, then the probability that the new k -core has less than n − h ( n ) vertices goes to zero, for any function h ( n ) → ∞ .