The number of connected sparsely edged graphs. IV large nonseparable graphs
Elizabeth Mary Wright · Journal of Graph Theory · 1983
Abstract The number of nonseparable graphs on n labeled points and q lines is u(n, q). In the second paper of this series an exact formula for u(n, n + k) was found for general n and successive (small) k. The method would give an asymptotic approximation for fixed k as n → ∞. Here an asymptotic approximation to u(n, n + k) is found when k = O(n1/2) and an approximation to logu(n, n + k) when k < (1 ‐ ϵ)(1/3 n)1/2. The problem of finding an approximation to u(n, q) when (q ‐ n)/n1/2 → + → and q/n ‐ 1/2 logn ‐ 1/2 log logn → ‐ ∞ is open.