Article ID Journal Published Year Pages File Type
8903165 Discrete Mathematics 2018 11 Pages PDF
Abstract
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 minimally 1-tough graph the minimum degree δ(G)=2. We show that in every minimally 1-tough graph δ(G)≤n3+1. We also prove that every minimally 1-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number t any graph can be embedded as an induced subgraph into a minimally t-tough graph.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,