Asymptotic enumeration of 2-covers and line graphs

Simple item page
dc.creatorCameron, Peter
dc.creatorPrellberg, Thomas
dc.creatorStark, Dudley
dc.date2007-07-04
dc.date.accessioned2026-07-07T08:13:59Z
dc.date.available2026-07-07T08:13:59Z
dc.descriptionIn 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.
dc.identifierhttps://arxiv.org/abs/0707.0664
dc.identifierhttp://arxiv.org/abs/0707.0664
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/132968
dc.subjectCombinatorics
dc.titleAsymptotic enumeration of 2-covers and line graphs
dc.typetext

Files

Collections

arXiv