Asymptotic enumeration of 2-covers and line graphs

Details Asymptotic enumeration of 2-covers and line graphs Asymptotic enumeration of 2-covers and line graphs

2007-07-04

arxiv.org/abs/0707.0664v1

Mathematics

Combinatorics

Scientific paper

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(-\frac12\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(-[\frac12\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.

Affiliated with

Also associated with

No associations

Rating

Asymptotic enumeration of 2-covers and line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic enumeration of 2-covers and line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic enumeration of 2-covers and line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-547836