论图的坚韧度(Ⅱ)

ON THE TOUGHNESS OF GRAPHS(II)

连通图G的坚韧度,记作τ(G),定义为τ(G)=min{|S|/ω(G-S);S∈C(G)},其中ω(G-S)表示图G-S的连通分支数,C(G)表示图G中所有点割集构成的集合。本文解决了坚韧度τ(G)=τ的p阶连通图G可能具有的最大边数及相应图构造的方法和步骤。

The toughness, τ(G), of a connected graph G, is defined by τ(G) = mm{|S|/[w(G -S)}; S ∈ C(G)}, where w(G - S) denotes the number of components of G - S, C(G) denotes the collection of cut-sets of G. In this paper, the maximum graphical structure is obtained when the number p of vertices of a connected graph G and the toughness τ(G) =τ are given. Finally, The methods of constructing the sorts of graphs are also presented.