On the minimum degree of minimally 1-tough, triangle-free graphs and minimally 3/2-tough, claw-free graphs
Hui Ma, Xiao‐Min Hu, Weihua Yang · Discrete Mathematics · 2023
A graph G is minimally t -tough if the toughness of G is t and deletion of any edge from G decreases its toughness. Katona et al. conjectured that the minimum degree of any minimally t -tough graph is ⌈ 2 t ⌉ and gave some upper bounds on the minimum degree of the minimally t -tough graphs in [5] , [6] . In this paper, we show that a minimally 1-tough graph G with girth g ≥ 5 has minimum degree at most ⌊ n g + 1 ⌋ + g − 1 , and a minimally 1-tough graph with girth 4 has minimum degree at most n + 6 4 . We also prove that the minimum degree of minimally 3 2 -tough, claw-free graphs is 3.