Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

See

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

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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