树的断裂度的紧上界

A Sharp Upper Bound of Scatering Number for Trees

断裂度是图的哈密尔顿性和容错性的一个有效度量.对连通图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/Δ的余数和上整数.最后我们用例子说明这个上界是可达的.

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/Δd」;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）/Δ minmal integer more than Finally,we give examples to show the hound is sharp.