5
$\begingroup$

In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics.

For example it is stated that the number of all unlabeled graph is $\sim 2^{ n \choose 2}/n!$ and that almost all graphs are blocks. They also state that it's very likely that for all natural numbers $n$ almost all graphs are $n-$ connected (do not know if that is already proven or not).

The book is quite old and I assume there are many new results in this field. I am interested in the asymptotics for the number of graphs that are connected but not $2-$ connected. That is connected graphs with more than one block. In the mentioned book I was not able to find any function asymptotic to this quantity but I believe there could be some new result covering my question.

Anyone happens to be aware of it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

See

and references therein (in particular, to the Erdős–Rényi paper).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .