4
$\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?

$\endgroup$

1 Answer 1

6
$\begingroup$

See

http://www.math.uwaterloo.ca/~nwormald/papers/2connected.pdf

and references therein (in particular, to the Erdos/Renyi paper).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.