Counting connected graphs asymptotically |
| |
| Authors: | Remco van der Hofstad Joel Spencer |
| |
| Affiliation: | aDepartment of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands;bDepartment of Computer Science, Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., New York, NY 10012, USA |
| |
| Abstract: | ![]()
We find the asymptotic number of connected graphs with k vertices and k−1+l edges when k,l approach infinity, re-proving a result of Bender, Canfield and McKay. We use the probabilistic method, analyzing breadth-first search on the random graph G(k,p) for an appropriate edge probability p. Central is the analysis of a random walk with fixed beginning and end which is tilted to the left. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
