The number of connected sparsely edged graphs. III. Asymptotic results
Elizabeth Mary Wright · Journal of Graph Theory · 1980
Abstract The number of connected graphs on n labeled points and q lines (no loops, no multiple lines) is f(n,q). In the first paper of this series I showed how to find an (increasingly complicated) exact formula for f(n,n+k) for general n and successive k. The method would give an asymptotic approximation to f(n,n+k) for any fixed k as n → ∞. Here I find this approximation when k = o(n1/3), a much more difficult matter. The problem of finding an approximation to f(n,q) when q > n + Cn1/3 and (2 q/n) ‐ log n → ‐ ∞ is open.