Katona, Solt\'esz, and Varga showed that no induced subgraph can be excluded from the class of minimally tough graphs. In this paper, we consider the opposite question, namely which induced subgraphs, if any, must necessarily be present in each minimally $t$-tough graph. Katona and Varga showed that for any rational number $t \in (1/2,1]$, every minimally $t$-tough graph contains a hole. We complement this result by showing that for any rational number $t>1$, every minimally $t$-tough graph must contain either a hole or an induced subgraph isomorphic to the $k$-sun for some integer $k \ge 3$. We also show that for any rational number $t > 1/2$, every minimally $t$-tough graph must contain either an induced $4$-cycle, an induced $5$-cycle, or two independent edges as an induced subgraph.
翻译:Katona, Solt\'esz, 和 Varga 显示, 任何诱导的子图都无法从最难的图表类别中排除。 在本文中, 我们考虑的是相反的问题, 即诱导的子图( 如果有的话) 必须在每张最低的美元- tough 图表中出现。 Katona 和 Varga 显示, 对于任何合理的数字(1/2, 1美元), 每个最低的美元- tough 图表都包含一个洞。 我们通过显示, 对于任何合理的数字 $>1, 每张最小的美元- tough 图表必须包含一个洞或诱导的子图( $1 $1 $), 或者每个最小的美元- tough 图表必须包含一个诱导的 4 美元周期, 诱导的 5 美元- 周期, 或者两个独立的边框作为诱导的子图 。