| 变更图的边添加 |
| |
| 引用本文： | NAJIM Alaa A,徐俊明. 变更图的边添加[J]. 中国科学技术大学学报, 2005, 35(6): 725-731 |
| |
| 作者姓名： | NAJIM Alaa A 徐俊明 |
| |
| 作者单位： | 中国科学技术大学数学系,安徽,合肥,230026 |
| |
| 基金项目： | Supported by NNSF of China （10271114）. |
| |
| 摘 要： | 证明了:对任何整数t≥6和d≥2,从一条长为d的简单路通过添加t条边后得到的图的最小直径上界为[d-2/t 1] 2,如果d∈J'(t,k)={2k(t 1) 1,2k(t 1) 2,2k(t 1)-t 1}∪{2k(t 1)-t h:h=6,7,…,t};其他情形为[d-2/t 1] 1.这个证明改进了已知结果,而且[d-2/t 1] 1是最好的上界.
|
| 关 键 词： | 直径 变更图 边添加 |
| 文章编号： | 0253-2778（2005）06-0725-07 |
| 收稿时间： | 2004-09-08 |
| 修稿时间： | 2005-10-15 |
On Edge Addition of Altered Graphs |
| |
| NAJIM Alaa A,XU Jun-ming. On Edge Addition of Altered Graphs[J]. Journal of University of Science and Technology of China, 2005, 35(6): 725-731 |
| |
| Authors: | NAJIM Alaa A XU Jun-ming |
| |
| Affiliation: | Department of Mathematics, University of Science and Technology of China, He f ei 230026, China |
| |
| Abstract: | This paper proves that, for any integerst ≥ 6 and d ≥ 2, the upper bound of minimum diameter of a connected graph obtained from a single path of length d by addingtextra edges is[d-2/t+1]+ 2 for d ∈ I' (t,k) = {2k(t + 1) + 1,2k(t + 1) +2,2k(t+1)-t+1} U {2k(t+1)-t+h:h=6,7,……, t} and[d-2/t+1]+1 otherwise for any integer k ≥ 1, which improves the known results. The bound[d-2/t+1]+1 is best possible. |
| |
| Keywords: | diameter altered graph edge addition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
