Connectivity for random graphs from a weighted bridge-addable class

Details Connectivity for random graphs from a weighted bridge-addable class Connectivity for random graphs from a weighted bridge-addable class

2012-03-15

arxiv.org/abs/1203.3398v1

Mathematics

Combinatorics

19 pages

Scientific paper

There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general `bridge-addable' class of graphs -- if a graph is in the class and u and v are vertices in different components then the graph obtained by adding an edge (bridge) between u and v must also be in the class. Various bounds are known concerning the probability of a random graph from such a class being connected or having many components, sometimes under the additional assumption that bridges can be deleted as well as added. Here we improve or amplify or generalise these bounds. The generalisation is to consider `weighted' random graphs, sampled from a suitable more general distribution, where the focus is on the bridges.

Affiliated with

Also associated with

No associations

Rating

Connectivity for random graphs from a weighted bridge-addable class does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Connectivity for random graphs from a weighted bridge-addable class, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity for random graphs from a weighted bridge-addable class will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31094