Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Enumeration and asymptotic properties of unlabeled outerplanar graphs. | Enumeration and asymptotic properties of unlabeled outerplanar graphs Manuel Bodirsky1 Eric Fusy2 Mihyun Kang1 3 and Stefan Vigerske1 1Humboldt-Universitat zu Berlin Institut fur Informatik Unter den Linden 6 10099 Berlin Germany bodirsky kangg@ stefan@ 2Projet Algo INRIA Rocquencourt B. P. 105 78153 Le Chesnay Cedex France Submitted Mar 15 2007 Accepted Aug 1 2007 Published Sep 14 2007 Mathematics Subject Classihcation 05C88 Abstract We determine the exact and asymptotic number of unlabeled outerplanar graphs. The exact number gn of unlabeled outerplanar graphs on n vertices can be computed in polynomial time and gn is asymptotically g n 5 2p n where g and p-1 can be approximated. Using our enumerative results we investigate several statistical properties of random unlabeled outerplanar graphs on n vertices for instance concerning connectedness the chromatic number and the number of edges. To obtain the results we combine classical cycle index enumeration with recent results from analytic combinatorics. Keywords unlabeled outerplanar graphs dissections combinatorial enumeration cycle index asymptotic estimates singularity analysis 1 Introduction and results Singularity analysis is very successful for the asymptotic enumeration of combinatorial structures 14 once a sufficiently good description of the corresponding generating functions is provided. When we count unlabeled structures . when we count the structures 3Research supported by the Deutsche Forschungsgemeinschaft DFG Pr 296 THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R66 1 up to isomorphism the potential symmetries of the structures often require a more powerful tool than generating functions . cycle index sums introduced by Pólya 30 . From the cycle index sums for classes of combinatorial structures we can obtain the corresponding generating functions to which we can then apply singularity analysis. However when .
