Minimally t-Tough Graphs

A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Kriesell conjectured that for every minimally1-tough graph the minimum degree δ(G) = 2. It is natural to generalize this for other t values: Every minimally t-tough graph has a vertex of degree ceil(2t). In the present talk we investigate different questions related to this conjecture. The conjecture seems to be hard to prove, so we tried to prove it for some special graph classes. It turned out, that in some cases the conjecture is true because there are very few graphs that satisfy the conditions. On the other hand, we have evidence using complexity theory, that this is not the situation for some other graph classes. Many open questions remain.

This is joint work with Kitti Varga, István Kovács, Dániel Soltész.