Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903165 | Discrete Mathematics | 2018 | 11 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Gyula Y. Katona, Dániel Soltész, Kitti Varga,