Connectivity for random graphs from a weighted bridge-addable class
There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general 'bridge-addable' class of graphs - if a graph is in the class and u and v are vertices in diffe...
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | Journal article |
| اللغة: | English |
| منشور في: |
2012
|
| _version_ | 1826274871453155328 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | There has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general 'bridge-addable' class of graphs - if a graph is in the class and u and v are vertices in different components then the graph obtained by adding an edge (bridge) between u and v must also be in the class. Various bounds are known concerning the probability of a random graph from such a class being connected or having many components, sometimes under the additional assumption that bridges can be deleted as well as added. Here we improve or amplify or generalise these bounds. For example, we see that the expected number of vertices left when we remove a largest component is less than 2. The generalisation is to consider 'weighted' random graphs, sampled from a suitable more general distribution, where the focus is on the bridges. |
| first_indexed | 2024-03-06T22:50:04Z |
| format | Journal article |
| id | oxford-uuid:5e75d79d-747d-4cf2-9d6b-fc34c9d7bc89 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T22:50:04Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:5e75d79d-747d-4cf2-9d6b-fc34c9d7bc892022-03-26T17:40:58ZConnectivity for random graphs from a weighted bridge-addable classJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:5e75d79d-747d-4cf2-9d6b-fc34c9d7bc89EnglishSymplectic Elements at Oxford2012McDiarmid, CThere has been much recent interest in random graphs sampled uniformly from the n-vertex graphs in a suitable structured class, such as the class of all planar graphs. Here we consider a general 'bridge-addable' class of graphs - if a graph is in the class and u and v are vertices in different components then the graph obtained by adding an edge (bridge) between u and v must also be in the class. Various bounds are known concerning the probability of a random graph from such a class being connected or having many components, sometimes under the additional assumption that bridges can be deleted as well as added. Here we improve or amplify or generalise these bounds. For example, we see that the expected number of vertices left when we remove a largest component is less than 2. The generalisation is to consider 'weighted' random graphs, sampled from a suitable more general distribution, where the focus is on the bridges. |
| spellingShingle | McDiarmid, C Connectivity for random graphs from a weighted bridge-addable class |
| title | Connectivity for random graphs from a weighted bridge-addable class |
| title_full | Connectivity for random graphs from a weighted bridge-addable class |
| title_fullStr | Connectivity for random graphs from a weighted bridge-addable class |
| title_full_unstemmed | Connectivity for random graphs from a weighted bridge-addable class |
| title_short | Connectivity for random graphs from a weighted bridge-addable class |
| title_sort | connectivity for random graphs from a weighted bridge addable class |
| work_keys_str_mv | AT mcdiarmidc connectivityforrandomgraphsfromaweightedbridgeaddableclass |