3
$\begingroup$

Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph.

I want to find out the minimum number of edges that I must remove randomly to disconnect the graph. Also the value of $p$ where I can disconnect the graph by removing the least number of edges.

$\endgroup$
3
  • 2
    $\begingroup$ What research have you done? $\endgroup$ – Yuval Filmus Nov 12 '14 at 4:00
  • 4
    $\begingroup$ This is just the standard Erdős–Rényi $G(n,p)$ model, except that, by starting with a complete graph and deleting edges, you're looking at $G(n,1-p)$. $\endgroup$ – David Richerby Nov 12 '14 at 8:25
  • $\begingroup$ Minimum number is denitely $n$, are you looking for the estimated number of edges that need to be removed? $\endgroup$ – orezvani Nov 13 '14 at 0:19
3
$\begingroup$

For your first question, an empty graph becomes connected roughly when $n\log n$ random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper On the evolution of random graphs, and recounted in textbooks on random graphs.

Your second question is not stated precisely and so is difficult to answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.