Premium
Toughness and Vertex Degrees
Author(s) -
Bauer D.,
Broersma H. J.,
van den Heuvel J.,
Kahl N.,
Schmeichel E.
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21639
Subject(s) - mathematics , monotone polygon , vertex (graph theory) , combinatorics , graph , integer (computer science) , discrete mathematics , computer science , geometry , programming language
We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t ‐tough. We first give a best monotone theorem when t ≥ 1 , but then show that for any integer k ≥ 1 , a best monotone theorem for t = 1 k ≤ 1 requires at least f ( k ) · | V ( G ) | nonredundant conditions, where f ( k ) grows superpolynomially as k → ∞ . When t < 1 , we give an additional, simple theorem for G to be t ‐tough, in terms of its vertex degrees.