XIX.—Asymptotic enumeration of connected graphs
- 1 January 1970
- journal article
- research article
- Published by Cambridge University Press (CUP) in Proceedings of the Royal Society of Edinburgh. Section A. Mathematical and Physical Sciences
- Vol. 68 (4) , 298-308
- https://doi.org/10.1017/s0080454100008451
Abstract
The number of different connected graphs (with some property P) on n labelled nodes with q edges is fnq. Again Fnq is the number of graphs on n labelled nodes with q edges, each of whose connected components has property P. We consider 8 types of graph for which . We use a known relation between the generating functions of fnq and Fnq to find an asymptotic expansion of fnq in terms of binomial coefficients, valid if (q – ½n log n)/n→∞ as n→∞. This condition is also necessary for the existence of an asymptotic expansion of this kind.Keywords
This publication has 2 references indexed in Scilit:
- On random graphs. I.Publicationes Mathematicae Debrecen, 2022
- Enumeration Of Labelled GraphsCanadian Journal of Mathematics, 1956