2012/03/09 by Cristiane M. Sato, Sato, Cristiane M. · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1203.2209
openalex publication_date 2012/03/09 · arxiv created 2012/09/11 · arxiv updated 2012/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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 seem 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 converges to k, then the new k-core is empty with probability 1+o(1). We define a constant c(k)' such that when k+epsilon < c < c(k)'- epsilon, the new k-core is empty with probability bounded away from zero and, if c > c(k)'+ psi with psi = omega(n-1/4), psi(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 every h(n) = omega(1/psi).