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. Constructing a minimally t-tough graph and studying its structural characteristics are of great significance in theory and applications. This paper proves that several kinds of Cartesian product graphs and line graphs are minimally t-tough and also construct a class of k-regular, and minimally k/2-tough graphs.
展开▼
