On the robustness of random k-cores

Details On the robustness of random k-cores On the robustness of random k-cores

2012-03-09

arxiv.org/abs/1203.2209v1

Mathematics

Combinatorics

Scientific paper

The k-core of a graph is its maximal subgraph with minimum degree at least k. In this paper, we address robustness questions about the k-core. 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\to k$, then the new k-core is empty with probability $1+o(1)$. We define a constant $c_k'$ such that when $k+\eps< c < c_k'-\eps$, the new k-core is empty with probability bounded away from zero and, if $c > c_k'+ \psi(n)$ with $\psi(n) = \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(\psi(n)^{-1})$.

Affiliated with

Also associated with

No associations

Rating

On the robustness of random k-cores does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the robustness of random k-cores, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the robustness of random k-cores will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488129