论图的坚韧度(Ⅱ)  

ON THE TOUGHNESS OF GRAPHS(II)

作　　者：许进[1] 

机构地区：[1]西安电子科技大学电子工程研究所,西安710071

出　　处：《电子与信息学报》1996年第S1期28-33,共6页Journal of Electronics & Information Technology

基　　金：中国博士后科学基金

摘　　要：连通图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.

关 键 词：图的坚韧度 坚韧集 最大边数 构造 

分 类 号：O157.5[理学—数学]