2025/05/13 by Hasanvand, Morteza
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.08131
Kriesel conjectured that every minimally 1-tough graph has a vertex with degree precisely 2. Katona and Varga (2018) proposed a generalized version of this conjecture which says that every minimally t-tough graph has a vertex with degree precisely \lceil 2t\rceil, where t is a positive real number. This conjecture has been recently verified for several families of graphs. For example, Ma, Hu, and Yang (2023) confirmed it for claw-free minimally 3/2-tough graphs. Recently, Zheng and Sun (2024) disproved this conjecture by constructing a family of 4-regular graphs with toughness approaching to 1. In this paper, we disprove this conjecture for planar graphs and their line graphs. In particular, we construct an infinite family of minimally t-tough non-regular claw-free graphs with minimum degree close to thrice their toughness. This construction not only disproves a renewed version of Generalized Kriesel's Conjecture on non-regular graphs proposed by Zheng and Sun (2024), it also gives a supplement to a result due to Ma, Hu, and Yang (2023) who proved that every minimally t-tough claw-free graph with t≥ 2 has a vertex of degree at most 3t+ \lceil (t-5)/3\rceil. Moreover, we conjecture that there is not a fixed constant c such that every minimally t-tough graph has minimum degree at most \lceil c t \rceil.