pith. sign in

arxiv: 1204.4580 · v1 · pith:UBO73Y2Ynew · submitted 2012-04-20 · 🧮 math.CO

The number of graphs of given diameter

classification 🧮 math.CO
keywords diameterasymptoticformulagivengraphgraphsnumbertypical
0
0 comments X
read the original abstract

In this paper it is proved that there are constants 0< c_2< c_1 such that an asymptotic formula can be given for the the number of (labeled) n-vertex graphs of diameter d whenever n tends to infinity and 2 < d < n - c_1 (log n). A typical graph of diameter d consists of a combination of an induced path of length d and a highly connected block of size n-d+3. In the case d > n- c_2(log n) another asymptotic formula is calculated and the typical graph has a completely different snakelike structure.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.