Asymptotic enumeration of 2-covers and line graphs

Abstract

In this paper we find asymptotic enumerations for the number of line graphs on $n$-labelled vertices and for different types of related combinatorial objects called 2-covers. We find that the number of 2-covers, $s_n$, and proper 2-covers, $t_n$, on $[n]$ both have asymptotic growth $$s_n\sim t_n\sim B_{2n}{2}^{-n}\exp (-\frac{1}{2}\log (2n/\log n))=B_{2n}{2}^{-n}\sqrt{\frac{\log n}{2n}},$$ where $B_{2n}$ is the $2n$th Bell number, while the number of restricted 2-covers, $u_n$, restricted, proper 2-covers on $[n]$, $v_n$, and line graphs $l_n$, all have growth $$u_n\sim v_n\sim l_n\sim B_{2n}{2}^{-n}{n}^{-1/2}\exp (-[\frac{1}{2}\log (2n/\log n){]}^2).$$ In our proofs we use probabilistic arguments for the unrestricted types of 2-covers and and generating function methods for the restricted types of 2-covers and line graphs.