论文标题
在随机边缘扰动下脆弱的次要超声酮参数
Fragile minor-monotone parameters under random edge perturbation
论文作者
论文摘要
我们对所需的随机边数的数量进行定量分析〜$ h $，以显着增加所得图〜$ r $的天然次要次要图形参数。具体来说，我们表明，如果仅添加几个随机边缘，从连接的图$ h $获得$ r $，则$ r $的树宽度，属和Hadwiger的数量将变得非常大，而不论〜$ h $的结构如何。
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$.
