论文标题
最少韧性的最小剧烈弦图，最多$ 1/2 $
Minimally tough chordal graphs with toughness at most $1/2$
论文作者
论文摘要
让$ t $成为一个正实数。如果删除任何最多可断开图形叶子的$ | s |/t $组件，则将图称为\ emph {$ t $ -tough}。图的韧性是该图为$ t $ tough的最大$ t $。如果图形的韧性为$ t $，则图最少是$ t $ - 限制，并且从图中删除任何边缘会降低韧性。图形为\ emph {conordal}，如果它不包含至少$ 4 $的诱发周期。 我们表征了所有$ t \ le 1/2 $的最小$ t $ tough，和弦图。作为推论，最小$ t $ tough的表征是为$ t \ le 1/2 $获得的间隔图。
Let $t$ be a positive real number. A graph is called \emph{$t$-tough} if the removal of any vertex set $S$ that disconnects the graph leaves at most $|S|/t$ components. The toughness of a graph is the largest $t$ for which the graph is $t$-tough. A graph is minimally $t$-tough if the toughness of the graph is $t$ and the deletion of any edge from the graph decreases the toughness. A graph is \emph{chordal} if it does not contain an induced cycle of length at least $4$. We characterize the minimally $t$-tough, chordal graphs for all $t\le 1/2$. As a corollary, a characterization of minimally $t$-tough, interval graphs is obtained for $t\le 1/2$.
