Random unlabelled graphs containing few disjoint cycles.
We call a set B of vertices in a graph G a blocker if the graph G - B obtained from G by deleting the vertices in B has no cycles. The classical Erdos-Pósa theorem (1965) states that for each positive integer k there is a positive integer f(k) such that in each graph G which contains at most k pairw...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2011
|
| _version_ | 1797065307643183104 |
|---|---|
| author | Kang, M McDiarmid, C |
| author_facet | Kang, M McDiarmid, C |
| author_sort | Kang, M |
| collection | OXFORD |
| description | We call a set B of vertices in a graph G a blocker if the graph G - B obtained from G by deleting the vertices in B has no cycles. The classical Erdos-Pósa theorem (1965) states that for each positive integer k there is a positive integer f(k) such that in each graph G which contains at most k pairwise vertex-disjoint cycles, there is a blocker B of size at most f(k).We show that, amongst all unlabelled n-vertex graphs with at most k disjoint cycles, all but an exponentially small proportion have a unique blocker of size k. We also determine the asymptotic number and properties of such graphs. For example we study the limiting probability that such graphs are connected, the limiting average number of vertices not in the giant component, and the limiting distribution of the chromatic number. Further, we give more detailed results concerning graphs with no two disjoint cycles.These results complement recent results for labelled graphs by Kurauskas and the second author. © 2010 Wiley Periodicals, Inc. |
| first_indexed | 2024-03-06T21:26:47Z |
| format | Journal article |
| id | oxford-uuid:435fccdc-fb41-4fd9-a32f-45c336750654 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:26:47Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:435fccdc-fb41-4fd9-a32f-45c3367506542022-03-26T14:54:56ZRandom unlabelled graphs containing few disjoint cycles.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:435fccdc-fb41-4fd9-a32f-45c336750654EnglishSymplectic Elements at Oxford2011Kang, MMcDiarmid, CWe call a set B of vertices in a graph G a blocker if the graph G - B obtained from G by deleting the vertices in B has no cycles. The classical Erdos-Pósa theorem (1965) states that for each positive integer k there is a positive integer f(k) such that in each graph G which contains at most k pairwise vertex-disjoint cycles, there is a blocker B of size at most f(k).We show that, amongst all unlabelled n-vertex graphs with at most k disjoint cycles, all but an exponentially small proportion have a unique blocker of size k. We also determine the asymptotic number and properties of such graphs. For example we study the limiting probability that such graphs are connected, the limiting average number of vertices not in the giant component, and the limiting distribution of the chromatic number. Further, we give more detailed results concerning graphs with no two disjoint cycles.These results complement recent results for labelled graphs by Kurauskas and the second author. © 2010 Wiley Periodicals, Inc. |
| spellingShingle | Kang, M McDiarmid, C Random unlabelled graphs containing few disjoint cycles. |
| title | Random unlabelled graphs containing few disjoint cycles. |
| title_full | Random unlabelled graphs containing few disjoint cycles. |
| title_fullStr | Random unlabelled graphs containing few disjoint cycles. |
| title_full_unstemmed | Random unlabelled graphs containing few disjoint cycles. |
| title_short | Random unlabelled graphs containing few disjoint cycles. |
| title_sort | random unlabelled graphs containing few disjoint cycles |
| work_keys_str_mv | AT kangm randomunlabelledgraphscontainingfewdisjointcycles AT mcdiarmidc randomunlabelledgraphscontainingfewdisjointcycles |