On the robustness of random kk-cores

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