图的韧性

一个连通图 被称为 -韧的，如果对于每个整数 ，图 不能通过移除少于 个顶点而被分割成 个不同的连通分量。图 的韧性 被定义为最大的实数，使得从 中删除任意 个顶点后，得到的图要么是连通的，要么最多有 个连通分量。韧性也可以简单地定义为

其中 是连通分量的数量，最小值取自 的所有顶点割 (Chvátal 1973)。

这个性质被称为“韧性”，因为它衡量了一个图的各个部分“紧密地结合在一起”的程度 (Chvátal 1973)。 特别地，每个 -韧的图也是 -顶点连通的。

一个图是完全图 当且仅当 (Chvátal 1973)。

虽然 Chvátal (1973) 将不连通图的 定义为 0，但使用顶点割的定义作为增加连通分量数量的割，该定义可以应用于给出不连通图的明确定义的韧性。

韧性的边割类似物被称为图强度。

识别一个图是否为 1-韧是 NP-困难 的 (Bauer 等人 1990)。

请注意，必须考虑所有顶点割（而不仅仅是最小顶点割）。例如，在 3-齿轮图 的情况下， 是大小为 2 的最小顶点割，移除后留下两个分量，比率为 ，而移除大小为 3 的顶点割 会留下 4 个分量，比率为 3/4，这是可能的最小值。

Chvátal (1973) 表明，完全二分图 (其中 ) 的韧性为 ，而车图 的韧性为 。

每个哈密顿图都是 1-韧的（即韧性 ），但存在反例，最小的反例在 7 个顶点上，一个非哈密顿图的韧性为 1。Chvátal (1973) 推测，所有韧性大于 3/2 的图都是哈密顿图，但 Bauer 等人 (2000) 驳斥了这一推测，他们表明并非每个 2-韧的图都是哈密顿图。Chvátal 的韧性猜想认为存在一个韧性阈值 ，高于该阈值 -韧的图始终是哈密顿图；其真假仍未解决 (Bauer 等人 2000)。

韧性大于 1 的小型非哈密顿图总结在下表中。

韧性为 的非哈密顿图
(1,1)-Blanusa snark	8/7
各种 -次哈密顿图	7/6
Sousselier 图，16-Lindgren-Sousselier 图，各种 -次哈密顿图	6/5
(13,1)-次哈密顿图，Tietze's 图	5/4
(1,2)-Blanusa snark，各种 -次哈密顿图	9/7
Petersen 图	4/3