The number of sparsely edged labelled Hamiltonian graphs
Elizabeth Mary Wright · Glasgow Mathematical Journal · 1983
An (n, q) graph is a graph on n labelled points and q lines, no loops and no multiple lines. We write N = ½n(n – 1), B(a, b) = a!/{b!(a – b)!} and B(a, 0) = 1, so that there are just B(N, q)different (n, q) graphs. Again h(n, q) is the number of Hamiltonian (n, q) graphs. Much attention has been devoted to the problem of determining for which q = q(n) “almost all” (n, q) graphs are Hamiltonian, i.e. for which q we have as n → ∞. I proved [8, Theorem 4] that qn–3/2; → ∞ is a sufficient condition by showing that, for such q, almost all (n, q) graphs have about the average number of Hamiltonian circuits (H.c.s).