Fragile minor-monotone parameters under random edge perturbation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908765550280704 |
|---|---|
| author | Kang, Dong Yeap Kang, Mihyun Kim, Jaehoon Oum, Sang-il |
| author_facet | Kang, Dong Yeap Kang, Mihyun Kim, Jaehoon Oum, Sang-il |
| contents | We conduct a quantitative analysis of how many random edges need to be added to a base graph $H$ in order to significantly increase natural minor-monotone graph parameters of the resulting graph $R$. Specifically, we show that if $R$ is obtained from a connected graph $H$ by adding only a few random edges, the tree-width, genus, and Hadwiger number of $R$ become very large, irrespective of the structure of $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_09897 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Fragile minor-monotone parameters under random edge perturbation Kang, Dong Yeap Kang, Mihyun Kim, Jaehoon Oum, Sang-il Combinatorics We conduct a quantitative analysis of how many random edges need to be added to a base graph $H$ in order to significantly increase natural minor-monotone graph parameters of the resulting graph $R$. Specifically, we show that if $R$ is obtained from a connected graph $H$ by adding only a few random edges, the tree-width, genus, and Hadwiger number of $R$ become very large, irrespective of the structure of $H$. |
| title | Fragile minor-monotone parameters under random edge perturbation |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2005.09897 |