Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability of graph connectivity

  1. Aug 28, 2004 #1
    Hi guys
    I am Samir. I am new to this group and need some help regarding a question that involves probability of connectivity in graphs.

    The problem can be stated as:

    Given a random graph G(n,p) where n is number of nodes in the graph and p is the probability that an edge exits between two nodes, (when p=0 graph does not have any edges and when p = 1 graph is fully connected.) then if i take a subgraph of this random graph based on criteria that all the nodes of this subgraph are at a particular distance from one fixed node, then what is the probability that this subgraph is connected? I want to know whether this probability will be less than p, and if yes how much less?

    I hope this makes my question clear.


  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted