Random Graphs from a Minor-Closed Class.
A minor-closed class of graphs is addable if each excluded minor is 2-connected. We see that such a class A of labelled graphs has smooth growth; and, for the random graph R n sampled uniformly from the n-vertex graphs in A, the fragment not in the giant component asymptotic...
| Huvudupphovsman: | |
|---|---|
| Materialtyp: | Journal article |
| Språk: | English |
| Publicerad: |
2009
|
| _version_ | 1826282733250281472 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | A minor-closed class of graphs is addable if each excluded minor is 2-connected. We see that such a class A of labelled graphs has smooth growth; and, for the random graph R n sampled uniformly from the n-vertex graphs in A, the fragment not in the giant component asymptotically has a simple 'Boltzmann Poisson distribution'. In particular, as n → ∞ the probability that R n is connected tends to 1/A(ρ), where A(x) is the exponential generating function for A and ρ is its radius of convergence. © 2009 Cambridge University Press. |
| first_indexed | 2024-03-07T00:48:18Z |
| format | Journal article |
| id | oxford-uuid:85743fad-0945-4861-9716-03bf232bbd56 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T00:48:18Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | oxford-uuid:85743fad-0945-4861-9716-03bf232bbd562022-03-26T21:57:43ZRandom Graphs from a Minor-Closed Class.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:85743fad-0945-4861-9716-03bf232bbd56EnglishSymplectic Elements at Oxford2009McDiarmid, CA minor-closed class of graphs is addable if each excluded minor is 2-connected. We see that such a class A of labelled graphs has smooth growth; and, for the random graph R n sampled uniformly from the n-vertex graphs in A, the fragment not in the giant component asymptotically has a simple 'Boltzmann Poisson distribution'. In particular, as n → ∞ the probability that R n is connected tends to 1/A(ρ), where A(x) is the exponential generating function for A and ρ is its radius of convergence. © 2009 Cambridge University Press. |
| spellingShingle | McDiarmid, C Random Graphs from a Minor-Closed Class. |
| title | Random Graphs from a Minor-Closed Class. |
| title_full | Random Graphs from a Minor-Closed Class. |
| title_fullStr | Random Graphs from a Minor-Closed Class. |
| title_full_unstemmed | Random Graphs from a Minor-Closed Class. |
| title_short | Random Graphs from a Minor-Closed Class. |
| title_sort | random graphs from a minor closed class |
| work_keys_str_mv | AT mcdiarmidc randomgraphsfromaminorclosedclass |