Enumeration and limit laws for series-parallel graphs

被引：40
作者：
Bodirsky, Manuel
Gimerez, Omer
Kang, Mihyun
Noy, Marc
机构：
[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany
[2] Univ Pompeu Fabra, Dept Tecnol, Barcelona 08003, Spain
[3] Univ Politecn Cataluna, Dept Matemat Aplicada 2, Barcelona 08034, Spain
来源：
EUROPEAN JOURNAL OF COMBINATORICS | 2007年 / 28卷 / 08期
关键词：
D O I：
10.1016/j.ejc.2007.04.011
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We show that the number g(n) of labelled series-parallel graphs on n vertices is asymptotically g(n) similar to g center dot n(-5/2)gamma(n)n!, where gamma and g are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that it is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs and for graphs not containing K-2.3 as a minor. (C) 2007 Elsevier Ltd. All rights reserved.
引用
收藏
页码：2091 / 2105
页数：15
相关论文
共 9 条
[1]  
BENDER EA, 2002, ELECT J COMBIN, V9
[2]  
BONICHON N, 2003, SPRINGER LECT NOTES, V2280, P81
[3]   SINGULARITY ANALYSIS OF GENERATING-FUNCTIONS [J].
FLAJOLET, P ;
ODLYZKO, A .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) :216-240
[4]  
FLAJOLET P, 1999, DISCRETE MATH
[5]  
FLAJOLET P, UNPUB ANAL COMBINATO
[6]   On the number of edges in random planar graphs [J].
Gerke, S ;
McDiarmid, A .
COMBINATORICS PROBABILITY & COMPUTING, 2004, 13 (02) :165-183
[7]  
GIMENEZ O, ASYMPTOTIC ENUMERATI
[8]  
Moon J. W., 1970, CAN MATH C
[9]  
WALSH TRS, 1982, J COMB THEORY B, V32, P1, DOI 10.1016/0095-8956(82)90072-7
1