On graphs with few disjoint t-star minors.
For fixed positive integers t ≥ 3 and k, consider the class of graphs which have at most k disjoint minors isomorphic to a t-star. We shall see that almost all of these graphs contain k vertices such that deleting them leaves a graph with no such minor. This holds for both labelled and unlabelled gr...
| Glavni autor: | |
|---|---|
| Format: | Journal article |
| Jezik: | English |
| Izdano: |
2011
|
| _version_ | 1826291346952945664 |
|---|---|
| author | McDiarmid, C |
| author_facet | McDiarmid, C |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | For fixed positive integers t ≥ 3 and k, consider the class of graphs which have at most k disjoint minors isomorphic to a t-star. We shall see that almost all of these graphs contain k vertices such that deleting them leaves a graph with no such minor. This holds for both labelled and unlabelled graphs, and answers a question of Bernardi, Noy and Welsh. We also estimate the asymptotic proportion of graphs in the class which do not have this property. © 2011 Elsevier Ltd. |
| first_indexed | 2024-03-07T02:58:02Z |
| format | Journal article |
| id | oxford-uuid:affc9fc6-e36b-4c51-b82c-ce6f9b7f7a01 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:58:02Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:affc9fc6-e36b-4c51-b82c-ce6f9b7f7a012022-03-27T03:53:14ZOn graphs with few disjoint t-star minors.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:affc9fc6-e36b-4c51-b82c-ce6f9b7f7a01EnglishSymplectic Elements at Oxford2011McDiarmid, CFor fixed positive integers t ≥ 3 and k, consider the class of graphs which have at most k disjoint minors isomorphic to a t-star. We shall see that almost all of these graphs contain k vertices such that deleting them leaves a graph with no such minor. This holds for both labelled and unlabelled graphs, and answers a question of Bernardi, Noy and Welsh. We also estimate the asymptotic proportion of graphs in the class which do not have this property. © 2011 Elsevier Ltd. |
| spellingShingle | McDiarmid, C On graphs with few disjoint t-star minors. |
| title | On graphs with few disjoint t-star minors. |
| title_full | On graphs with few disjoint t-star minors. |
| title_fullStr | On graphs with few disjoint t-star minors. |
| title_full_unstemmed | On graphs with few disjoint t-star minors. |
| title_short | On graphs with few disjoint t-star minors. |
| title_sort | on graphs with few disjoint t star minors |
| work_keys_str_mv | AT mcdiarmidc ongraphswithfewdisjointtstarminors |