Back to Search
Start Over
Fragile minor-monotone parameters under random edge perturbation
- Publication Year :
- 2020
-
Abstract
- We conduct a quantitative analysis on the number of random edges required to be added to a base graph~$H$ to significantly increase natural minor-monotone graph parameters in 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$.<br />Comment: 20 pages
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2005.09897
- Document Type :
- Working Paper