摘要
用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-2t+1+1.对某些t和d,确定了C(t,d)的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11:409-427].
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.
基金
Supported by NNSF of China(10271114).
