论文标题
最低限度的最低$ t $ tough图
The minimum degree of minimally $t$-tough graphs
论文作者
论文摘要
如果$ g $的韧性为$ t $，并且从$ g $中删除任何边缘的韧性会减少其韧性，则图表$ g $是最小的$ t $限制。 Katona等。推测任何最小$ t $ -tough图的最低度为$ \ lceil 2t \ rceil $，并以最低限度的最低限制在\ cite {katona，gyula}的最低限制上给出了一些上限。在本文中，我们表明，带有Girth $ g \ geq 5 $的最低限度的1-tough Graph $ g $最少$ \ lfloor \ lfloor \ frac {n} {n} {g+1} \ rfloor+g-1 $，最低额度为$ 4 $ $ 4 $ $ $ $ \ f frac} n+frac {6 $ $ 4 $};我们还证明，最小$ \ frac {3} 2 $ -tough无爪图的最低度为$ 3 $。
A graph $ G $ is minimally $ t $-tough if the toughness of $ G $ is $ t $ and deletion of any edge from $ G $ decreases its toughness. Katona et al. conjectured that the minimum degree of any minimally $ t $-tough graph is $ \lceil 2t\rceil $ and gave some upper bounds on the minimum degree of the minimally $ t $-tough graphs in \cite{Katona, Gyula}. In this paper, we show that a minimally 1-tough graph $ G $ with girth $ g\geq 5 $ has minimum degree at most $ \lfloor\frac{n}{g+1}\rfloor+g-1$, and a minimally $ 1 $-tough graph with girth $ 4 $ has minimum degree at most $ \frac{n+6}{4}$. We also prove that the minimum degree of minimally $\frac{3}2$-tough claw-free graphs is $ 3 $.
