| 树的断裂度的紧上界 |
| |
| 引用本文： | 张明瑜,王世英.树的断裂度的紧上界[J].太原师范学院学报(自然科学版),2008,7(3):1-4. |
| |
| 作者姓名： | 张明瑜 王世英 |
| |
| 作者单位： | 山西大学,数学科学学院,山西,太原,030006 |
| |
| 基金项目： | 国家自然科学基金，山西省自然科学基金 |
| |
| 摘 要： | 断裂度是图的哈密尔顿性和容错性的一个有效度量.对连通图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/Δ的余数和上整数.最后我们用例子说明这个上界是可达的.
|
| 关 键 词： | 断裂度 点断集 树 树叶 |
A Sharp Upper Bound of Scatering Number for Trees |
| |
| Zhang Mingyu,Wang Shiying.A Sharp Upper Bound of Scatering Number for Trees[J].Journal of Taiyuan Normal University:Natural Science Edition,2008,7(3):1-4. |
| |
| Authors: | Zhang Mingyu Wang Shiying |
| |
| Affiliation: | Zhang Mingyu Wang Shiying (School of Mathematical Sciences,Shanxi University,Taiyuan 030006,China) |
| |
| 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/Δ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. |
| |
| Keywords: | scattering number vertex cut tree leaf |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
