کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649163 | 1342444 | 2010 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Asymptotic enumeration of 2-covers and line graphs Asymptotic enumeration of 2-covers and line graphs](/preview/png/4649163.png)
A 2-cover is a multiset of subsets of [n]≔{1,2,…,n}[n]≔{1,2,…,n} such that each element of [n][n] lies in exactly two of the subsets. A 2-cover is called proper if all of the subsets are distinct, and is called restricted if any two of them intersect in at most one element.In this paper we find asymptotic enumerations for the number of line graphs on nn labelled vertices and for 2-covers.We find that the number snsn of 2-covers and the number tntn of proper 2-covers both have asymptotic growth sn∼tn∼B2n2−nexp(−12log(2n/logn)), where B2nB2n is the 2n2nth Bell number. Moreover, the numbers unun of restricted 2-covers on [n][n] and vnvn of restricted, proper 2-covers on [n][n] and lnln of line graphs all have growth un∼vn∼ln∼B2n2−nn−1/2exp(−[12log(2n/logn)]2).
Journal: Discrete Mathematics - Volume 310, Issue 2, 28 January 2010, Pages 230–240