From a complete random graph (ER graph) after deleting an edge randomly with some probability (p) in each step how many edge deletion occurs to make the graph disconnected or break the giant component? What will be the value of p to make minimum no. of edge deletion? Can we delay this phase transition by varying the value of p?

  • $\begingroup$ I find it hard to understand what you are asking. I think the question might be too terse. What do you mean by "when"? What exactly is the random process you want to study, and what exactly is the value you want to know about? What kind of result are you hoping for? Perhaps you want to know the expected number of deletions to disconnect the graph? Perhaps you want to know the value of p so that the graph is disconnected? Something else? It's hard to tell. Please edit to provide a lot more clarity. $\endgroup$ – D.W. Jun 1 at 18:57
  • $\begingroup$ Are you asking for the minimum cut in the giant component of $G(n,p)$, when it exists, focusing on values of $p$ for which the minimum cut is small? $\endgroup$ – Yuval Filmus Jun 2 at 8:18
  • $\begingroup$ The structure of the giant component is described in the following papers: Anatomy of a young giant component and Anatomy of the giant component $\endgroup$ – Yuval Filmus Jun 2 at 8:21
  • $\begingroup$ @Yuval yes...I want to know the minimum cut in the giant component focusing on values of p ( minimum cut is small). $\endgroup$ – Arnab Jun 3 at 11:33

Your Answer

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

Browse other questions tagged or ask your own question.