Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653501 | European Journal of Combinatorics | 2014 | 20 Pages |
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+ε