×

Connectivity of addable graph classes. (English) Zbl 1145.05033

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.

MSC:

05C40 Connectivity
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Balister, B. Bollobás, S. Gerke, The generalized Randić index of trees, J. Graph Theory, in press; P. Balister, B. Bollobás, S. Gerke, The generalized Randić index of trees, J. Graph Theory, in press
[2] McDiarmid, C.; Steger, A.; Welsh, D. J.A., Random planar graphs, J. Combin. Theory Ser. B, 93, 187-205 (2005) · Zbl 1056.05128
[3] McDiarmid, C.; Steger, A.; Welsh, D. J.A., Random graphs from planar and other addable classes, (Klazar, M.; Kratochvil, J.; Loebl, M.; Matousek, J.; Thomas, R.; Valtr, P., Topics in Discrete Mathematics, Dedicated to Jarik Nešetril on the occasion of his 60th birthday. Topics in Discrete Mathematics, Dedicated to Jarik Nešetril on the occasion of his 60th birthday, Algorithms Combin., vol. 26 (2006), Springer-Verlag: Springer-Verlag Berlin), 231-246 · Zbl 1119.05099
[4] Rényi, A., Some remarks on the theory of trees, Magyar Tud. Akad. Mat. Kutató Int. Közl, 4, 73-85 (1959) · Zbl 0093.37604
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.