toughness (644B)
1 # Toughness 2 3 https://en.wikipedia.org/wiki/Graph_toughness 4 5 A [graph] G is *t-tough* if, for every integer k>1, you must remove at least tk vertices to split G into at least k [connected_components] 6 7 Every [Hamiltonian_graph] is 1-tough: 8 https://en.wikipedia.org/wiki/Graph_toughness#Connection_to_Hamiltonicity 9 but the converse is false 10 11 It is [coNP_complete] to test whether a graph is 1-tough, and the same holds for t-toughness for any positive rational number t, cf https://en.wikipedia.org/wiki/Graph_toughness#Computational_complexity 12 13 [Chvátal's_toughness_conjecture] 14 15 Up: [graph] 16 17 See also: [graph_strength] 18 19 Aliases: graph toughness