Random graphs on surfaces.
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 hav...
| Váldodahkki: | |
|---|---|
| Materiálatiipa: | Journal article |
| Giella: | English |
| Almmustuhtton: |
Elsevier
2008
|
| _version_ | 1826260669757915136 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T19:09:21Z |
| format | Journal article |
| id | oxford-uuid:163f1bd7-88bc-4a2e-b105-d1a0b2021838 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:09:21Z |
| publishDate | 2008 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:163f1bd7-88bc-4a2e-b105-d1a0b20218382022-03-26T10:30:11ZRandom graphs on surfaces.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:163f1bd7-88bc-4a2e-b105-d1a0b2021838EnglishSymplectic Elements at OxfordElsevier2008McDiarmid, CCounting 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. |
| spellingShingle | McDiarmid, C Random graphs on surfaces. |
| title | Random graphs on surfaces. |
| title_full | Random graphs on surfaces. |
| title_fullStr | Random graphs on surfaces. |
| title_full_unstemmed | Random graphs on surfaces. |
| title_short | Random graphs on surfaces. |
| title_sort | random graphs on surfaces |
| work_keys_str_mv | AT mcdiarmidc randomgraphsonsurfaces |