几类极小t-坚韧图的构造

The Construction of Some Classes of Minimally t-Tough Graphs

若图G的坚韧度为t,且删除G中任意一条边后坚韧度减小,则称图G是极小t-坚韧的。构造极小t-坚韧图并研究其结构特性在理论和应用上都具有重要意义。证明了几类笛卡尔积图和线图的极小t-坚韧性,并构造出一类k-正则的极小k/2-坚韧图。

A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Constructing a minimally t-tough graph and studying its structural characteristics are of great significance in theory and applications. This paper proves that several kinds of Cartesian product graphs and line graphs are minimally t-tough and also construct a class of k-regular, and minimally k/2-tough graphs.