| 图的边添加和减少 |
| |
| 引用本文： | NAJIM Alaa A,徐俊明. 图的边添加和减少[J]. 中国科学技术大学学报, 2006, 36(3): 254-257 |
| |
| 作者姓名： | NAJIM Alaa A 徐俊明 |
| |
| 作者单位： | 中国科学技术大学数学系,安徽,合肥,230026 |
| |
| 基金项目： | Supported by NNSF of China （10271114）. |
| |
| 摘 要： | 用P（t,d）（或者C（t,d））表示从一条长为d的简单路（或者简单圈）通过添加t条边后得到图的最小直径.证明了：如果t和d满足条件t≥4且t＋4≤d≤t＋7,或者t=4且d=10k＋1（k≥1）,那么P（t,d）=[d-2D＋1]＋1.对某些t和d,确定了C（t,d）的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11：409-427].
|
| 关 键 词： | 直径 变更图 边添加 边减少 Schoone等的猜想 |
| 文章编号： | 0253-2778(2006)03-0254-04 |
| 收稿时间： | 2005-04-26 |
| 修稿时间： | 2006-03-01 |
Edge addition and edge deletion of graphs |
| |
| NAJIM Alaa A,XU Jun-ming. Edge addition and edge deletion of graphs[J]. Journal of University of Science and Technology of China, 2006, 36(3): 254-257 |
| |
| Authors: | NAJIM Alaa A XU Jun-ming |
| |
| Affiliation: | Department of Mathematics, University of Science and Technology of China, Hefei 230026, China |
| |
| Abstract: | Let P(t,d) (resp. C(t,d) ) be the minimum diameter of a connected graph obtained from a single path (resp. from a single circle) of length d by adding t extra edges. It is proved that P(t,d) = [d-2/t+1] + 1 if t and d satisfy the following conditions: t ≥ 4 and t+4≤d≤t+7,t=4 and d=10k+1 (k≥1). For some t and d, the exact value and the best lower bound of C(t,d)are determined, and so the conjecture of Schoone, et al [J. Graph Theory, 1987,11:409-427] is settled partially. |
| |
| Keywords: | diameter altered graph edge addition edge deletion Schoone et al's conjecture |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
