The toughness of a graph is defined as the largest real number such that for any set such that is disconnected, has at least times more elements than has components (unless is complete, in which case the toughness is defined to be infinite). A graph is said to be minimally tough if deleting any edge decreases the toughness. It is an open question whether there exists a minimally tough non-complete chordal graph with toughness exceeding . We initiate the study of minimally tough graphs in the larger class of weakly chordal graphs. We obtain complete classifications of minimally tough graphs in the following subclasses of weakly chordal graphs: co-chordal graphs whose complement has diameter at least , net-free co-chordal graphs, complements of forests, -free graphs, and complete multipartite graphs. Our approach leads to simple proofs of two results on minimally tough graphs due to Dallard, Fernández, Katona, Milanič, and Varga.

生成讲解博客的中文版本

生成AI智能校验的中文版本