samirg
Aug28-04, 11:21 PM
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.
Thanks
Samir
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.
Thanks
Samir