标题： 关于存在具有大最小度数的极小坚韧图的研究 显示英文标题

标题： On the existence of minimally tough graphs having large minimum degrees

摘要： 克赖泽尔猜想每个最小的$1$-坚韧图都有一个度数恰好为$2$的顶点。卡塔纳和瓦拉加（2018）提出了该猜想的一个广义版本，指出每个最小的$t$-坚韧图都有一个度数恰好为$\lceil 2t\rceil$的顶点，其中$t$是一个正实数。这一猜想最近已被验证了若干图类。例如，马、胡和杨（2023）确认了爪形最小的$3/2$-坚韧图符合这一猜想。 近日，郑和孙（2024）通过构造一族接近$1$的坚韧性趋近于$4$的正则图，反驳了这一猜想。在本文中，我们反驳了对于平面图及其线图的这一猜想。特别是，我们构造了一个无限族最小坚性为$t$的非正规无爪图，这些图的最小度数接近于其坚性的三倍。这一构造不仅反驳了郑和孙（2024）提出的关于非正规图的广义 Kriesel 猜想的一个新版本，还补充了马、胡和杨（2023）的结果，他们证明了每一个最小坚性为$t$的无爪图，如果具有$t\ge 2$，则存在一个度数不超过$3t+ \lceil (t-5)/3\rceil$的顶点。 此外，我们猜想不存在固定的常数$c$，使得每个最小度为$t$的图的最小度都不超过$\lceil c t \rceil$。 显示英文摘要

摘要： 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\ge 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$.