Journal article
Random graphs on surfaces.
- Abstract:
- Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1, ..., n}, then with probability tending to 1 as n → ∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components. © 2007 Elsevier Inc. All rights reserved.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 223.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jctb.2007.11.006
Authors
- Publisher:
- Elsevier
- Journal:
- J. Comb. Theory, Ser. B More from this journal
- Volume:
- 98
- Issue:
- 4
- Pages:
- 778-797
- Publication date:
- 2008-01-01
- DOI:
- EISSN:
-
1096-0902
- ISSN:
-
0095-8956
- Language:
-
English
- Keywords:
- UUID:
-
uuid:163f1bd7-88bc-4a2e-b105-d1a0b2021838
- Local pid:
-
pubs:102286
- Source identifiers:
-
102286
- Deposit date:
-
2012-12-19
Terms of use
- Copyright holder:
- Elsevier BV
- Copyright date:
- 2008
- Notes:
- Copyright 2007 Elsevier B.V. All rights reserved. Re-use of this article is permitted in accordance with the Terms and Conditions set out at http://www.elsevier.com/open-access/userlicense/1.0/
- Licence:
- Other
If you are the owner of this record, you can report an update to it here: Report update to this record