Connectivity and related properties for graph classes
<p>There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the cou...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2014
|
| Subjects: |
| _version_ | 1797072877300744192 |
|---|---|
| author | Weller, K Kerstin Weller |
| author2 | McDiarmid, C |
| author_facet | McDiarmid, C Weller, K Kerstin Weller |
| author_sort | Weller, K |
| collection | OXFORD |
| description | <p>There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course of studying random planar graphs. A class A is bridge-addable when the following holds: if we take any graph G in A and any pair u,v of vertices that are in different components in G, then the graph G′ obtained by adding the edge uv to G is also in A. It was shown that for a random graph sampled from a bridge-addable class, the probability that it is connected is always bounded away from 0, and the number of components is bounded above by a Poisson law. What happens if ’bridge-addable’ is replaced by something weaker? In this thesis, this question is explored in several different directions.</p> <p>After an introductory chapter and a chapter on generating function methods presenting standard techniques as well as some new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, decomposable and bridge-addable various properties are known (McDiarmid 2010), generalizing results for planar graphs. A minor-closed class is decomposable and bridge-addable if and only if all excluded minors are 2-connected. Chapter 3 presents a series of examples where the excluded minors are not 2-connected, analysed using generating functions as well as techniques from graph theory. This is a step towards a classification of connectivity behaviour for minor-closed classes of graphs. In contrast to the bridge-addable case, different types of behaviours are observed. Chapter 4 deals with a new, more general vari- ant of bridge-addability related to edge-expander graphs. We will see that as long as we are allowed to introduce ’sufficiently many’ edges between components, the number of components of a random graph can still be bounded above by a Pois- son law. In this context, random forests in Kn,n are studied in detail. Chapter 5 takes a different approach, and studies the class of labelled forests where some vertices belong to a specified stable set. A weighting parameter y for the vertices belonging to the stable set is introduced, and a graph is sampled with probability proportional to y*s where s is the size of its stable set. The behaviour of this class is studied for y tending to ∞. Chapters 6 concerns random graphs sampled from general decomposable classes. We investigate the minimum size of a component, in both the labelled and the unlabelled case.</p> |
| first_indexed | 2024-03-06T23:14:00Z |
| format | Thesis |
| id | oxford-uuid:667a139e-6d2c-4f67-8487-04c3a0136226 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:14:00Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | oxford-uuid:667a139e-6d2c-4f67-8487-04c3a01362262022-03-26T18:32:08ZConnectivity and related properties for graph classes Thesishttp://purl.org/coar/resource_type/c_db06uuid:667a139e-6d2c-4f67-8487-04c3a0136226CombinatoricsEnglishOxford University Research Archive - Valet2014Weller, KKerstin WellerMcDiarmid, C<p>There has been much recent interest in random graphs sampled uniformly from the set of (labelled) graphs on n vertices in a suitably structured class A. An important and well-studied example of such a suitable structure is bridge-addability, introduced in 2005 by McDiarmid et al. in the course of studying random planar graphs. A class A is bridge-addable when the following holds: if we take any graph G in A and any pair u,v of vertices that are in different components in G, then the graph G′ obtained by adding the edge uv to G is also in A. It was shown that for a random graph sampled from a bridge-addable class, the probability that it is connected is always bounded away from 0, and the number of components is bounded above by a Poisson law. What happens if ’bridge-addable’ is replaced by something weaker? In this thesis, this question is explored in several different directions.</p> <p>After an introductory chapter and a chapter on generating function methods presenting standard techniques as well as some new technical results needed later, we look at minor-closed, labelled classes of graphs. The excluded minors are always assumed to be connected, which is equivalent to the class A being decomposable - a graph is in A if and only if every component of the graph is in A. When A is minor-closed, decomposable and bridge-addable various properties are known (McDiarmid 2010), generalizing results for planar graphs. A minor-closed class is decomposable and bridge-addable if and only if all excluded minors are 2-connected. Chapter 3 presents a series of examples where the excluded minors are not 2-connected, analysed using generating functions as well as techniques from graph theory. This is a step towards a classification of connectivity behaviour for minor-closed classes of graphs. In contrast to the bridge-addable case, different types of behaviours are observed. Chapter 4 deals with a new, more general vari- ant of bridge-addability related to edge-expander graphs. We will see that as long as we are allowed to introduce ’sufficiently many’ edges between components, the number of components of a random graph can still be bounded above by a Pois- son law. In this context, random forests in Kn,n are studied in detail. Chapter 5 takes a different approach, and studies the class of labelled forests where some vertices belong to a specified stable set. A weighting parameter y for the vertices belonging to the stable set is introduced, and a graph is sampled with probability proportional to y*s where s is the size of its stable set. The behaviour of this class is studied for y tending to ∞. Chapters 6 concerns random graphs sampled from general decomposable classes. We investigate the minimum size of a component, in both the labelled and the unlabelled case.</p> |
| spellingShingle | Combinatorics Weller, K Kerstin Weller Connectivity and related properties for graph classes |
| title | Connectivity and related properties for graph classes |
| title_full | Connectivity and related properties for graph classes |
| title_fullStr | Connectivity and related properties for graph classes |
| title_full_unstemmed | Connectivity and related properties for graph classes |
| title_short | Connectivity and related properties for graph classes |
| title_sort | connectivity and related properties for graph classes |
| topic | Combinatorics |
| work_keys_str_mv | AT wellerk connectivityandrelatedpropertiesforgraphclasses AT kerstinweller connectivityandrelatedpropertiesforgraphclasses |