Connectivity Of Graphs


by samirg
Tags: connectivity, graphs
samirg
samirg is offline
#1
Aug26-04, 02:32 PM
P: 3
Hi Guys
I need some help on graph connectivity problem.
Given a graph is connected with probability p, what is the probablity that its subgraph is also connected?
In other words, we have to find the probablity that a subgraph of a connected graph is connected?

I hope i have made my question clear. Any help in this matter is really appreciated.

Thanks

Samir
Phys.Org News Partner Mathematics news on Phys.org
Math modeling handbook now available
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
matt grime
matt grime is offline
#2
Aug27-04, 05:01 AM
Sci Advisor
HW Helper
P: 9,398
It is impossible to answer the question without you saying more about the original graph. Given a "star graph" ie one central node and all vertices rays from it, then any subgraph must be connected, given another graph this will almost certainly fail to be true.
samirg
samirg is offline
#3
Aug27-04, 11:39 PM
P: 3
Quote Quote by matt grime
It is impossible to answer the question without you saying more about the original graph. Given a "star graph" ie one central node and all vertices rays from it, then any subgraph must be connected, given another graph this will almost certainly fail to be true.
Hi matt

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 question a bit clearer.

Thanks again

Samir

matt grime
matt grime is offline
#4
Aug29-04, 06:50 AM
Sci Advisor
HW Helper
P: 9,398

Connectivity Of Graphs


Double and triple posting is generally frowned upon.

Now you've introduced the word distance. the usual distance on graph is the length of the shortest path between nodes, which when defined explicitly tells you the subgraph you've picked must be connected (assuming the fixed node is in the subgraph).


Register to reply

Related Discussions
Ti-89 connectivity Calculators 8
Very simple calculus problem...graphs and velocity/time graphs to acceleration. Calculus & Beyond Homework 1
The Importance of Connectivity to Strong AI Medical Sciences 26
probability of graph connectivity Set Theory, Logic, Probability, Statistics 0
Connectivity of Graphs General Math 0