【摘要】 断裂度是图的哈密尔顿性和容错性的一个有效度量.对连通图G,它被定义为b(G)=max{w(G-S)-S:S是G的点断集},其中w(G-S)表示G-S的分支数.文章研究树的断裂度的上界,得到如下结论:设T是一棵阶为n(≥2),最大度为Δ的树.若r(n-1/Δ)≠1,则b(T)≤n-2「n-1/Δd」;若r(n-1/Δ)=1,则b(T)≤n-2「n-1/Δ」+1,其中r(n-1/Δ)和「n-1/Δ」分别表示n-1/Δ的余数和上整数.最后我们用例子说明这个上界是可达的.更多还原

【Abstract】 The scattering number is an effective measure of the hamiltonicity and vulnerability of graphs.For a connected graph G,it is defined as b(G)=max{w(G-S)-|S|:S is a vertex cut},where w(G-S)is the number of components of G-S.In this paper,we study the upper bound of scattering number for trees,and obtain the result as follows:Let T be a tree with order n(≥2) and naximum degree Δ.If r(n-1/Δ)≠1,then b(T)≤n-2「n-1/Δ」;If r(n-1/Δ)=1,then b(T)≤n-2「n-1/Δ」+1,where r(n-1/Δ) and 「n-1/Δ」 is the residue of n-1/Δ and the minmal integer more than n-1/Δ.Finally,we give examples to show the bound is sharp.更多还原