On the Maximum Degree of a Random Planar Graph.
Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is ⊖(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2008
|
| _version_ | 1797071339065966592 |
|---|---|
| author | McDiarmid, C Reed, B |
| author_facet | McDiarmid, C Reed, B |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | Let the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is ⊖(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface. © 2008 Cambridge University Press. |
| first_indexed | 2024-03-06T22:51:46Z |
| format | Journal article |
| id | oxford-uuid:5f097513-a439-4815-bdb5-e147feeb7b02 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:51:46Z |
| publishDate | 2008 |
| record_format | dspace |
| spelling | oxford-uuid:5f097513-a439-4815-bdb5-e147feeb7b022022-03-26T17:44:19ZOn the Maximum Degree of a Random Planar Graph.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5f097513-a439-4815-bdb5-e147feeb7b02EnglishSymplectic Elements at Oxford2008McDiarmid, CReed, BLet the random graph Rn be drawn uniformly at random from the set of all simple planar graphs on n labelled vertices. We see that with high probability the maximum degree of Rn is ⊖(ln n). We consider also the maximum size of a face and the maximum increase in the number of components on deleting a vertex. These results extend to graphs embeddable on any fixed surface. © 2008 Cambridge University Press. |
| spellingShingle | McDiarmid, C Reed, B On the Maximum Degree of a Random Planar Graph. |
| title | On the Maximum Degree of a Random Planar Graph. |
| title_full | On the Maximum Degree of a Random Planar Graph. |
| title_fullStr | On the Maximum Degree of a Random Planar Graph. |
| title_full_unstemmed | On the Maximum Degree of a Random Planar Graph. |
| title_short | On the Maximum Degree of a Random Planar Graph. |
| title_sort | on the maximum degree of a random planar graph |
| work_keys_str_mv | AT mcdiarmidc onthemaximumdegreeofarandomplanargraph AT reedb onthemaximumdegreeofarandomplanargraph |