Fragile minor-monotone parameters under a random edge perturbation
Dong Yeap Kang, Mihyun Kang, Jaehoon Kim, Sang‐il Oum · European Journal of Combinatorics · 2025
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$.