一类特殊坚韧图的性质

Properties of Some Class of Special Tough Graphs

连通图G的坚韧度定义为。如果G的坚韧度是t,并且删去G的任意一条边后其坚韧度减小,则称G是极小t-坚韧的。Matthews等证明了K1,3-free图的连通度是其坚韧度的2倍。本文证明了坚韧度为t的K1,n-free图的连通度不超过(n-1)t,且极小1-坚韧,K1,4-free图的连通度为2。此外,Kriesell猜想极小1-坚韧图的最小度是2。Katona等推广了上述猜想,极小t-坚韧图的最小度是 。本文证明了极小1/(n-1)-坚韧,K1,n-free图的最小度为1,其中n≥3。

The toughness of G is defined as . 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. Matthews et al. has proved that the connectivity of K1,3 -free graphs is twice its tough-ness. This paper shows that the connectivity of K1,n -free graphs with toughness t is at most , and the connectivity of minimally 1-tough, K1,4 -free graphs is 2. In addition, Kriesell con-jectured that the minimum degree of minimally 1-graphs is 2. Katona et al. proposed a generalized version of the conjecture that the minimum degree of minimally t-tough graph is . This paper proves that the minimum degree of minimally 1/(n-1)-tough, K1,n -free graphs is 1, where n≥3 .