Connectivity of addable graph classes (Q2483480)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Connectivity of addable graph classes |
scientific article |
Statements
Connectivity of addable graph classes (English)
0 references
28 April 2008
0 references
A non-empty class \(A\) of labeled graphs is weakly addable if the class is closed under the joining of an edge between any two distinct components in a graph of the class. Consider a non-empty subclass of \(A\) containing the graphs of \(n\) specified vertices. For sufficiently large \(n\), a new lower bound is given for the probability that a graph drawn uniformly at random from the subclass is connected. By extending the notion of addability to closeness under the addition of at most two edges between any two distinct components of a graph, it is proved that the random graph is connected with probability 1 as \(n\) tends to infinity.
0 references
connectivity
0 references
planar and other addable graph classes
0 references