关于图的边添加

给定任意正整数t和d(≥2),记P(t,d)为在直径d的路上加上t条边后所得图的最小直径.证明了:P(6,4)=1; 当d=5,6,7时有P(6,d)=2;当d=7(2k-1)+h(k≥1, 1≤h≤14) 时有(d)/(7)≤P(6,d)≤ (d)/(7)+2若h=7;(d)/(7)+1其他;当d=5,6,7,8时有P(7,d)=2;当d=8(2k-1)+h (k≥1,1≤h≤16)时有(d)/(8)≤P(7,d)≤ (d)/(8)若h=1;(d)/(8)+2若h=2,3,4,5,6,7,8;(d)/(8)+1其他.

On addition of edges of graphs

Given positive integers t and d(≥2), let P(t,d) denote the minimum diameter of a graph obtained by adding t extra edges to a path with diameter d. It was proved that P(6,4)=1, P(6,d)=2 for d=5,6,7, and (d)/(7)≤P(6,d)≤(d)/(7)+2if h=7;≤(d)/(7)+1otherwise,for d=7(2k-1)+h, where k≥1 and 1≤h≤14. Moreover, P(7,d)=2 for d=5,6,7,8, and(d)/(8)≤P(7,d)=(d)/(8)if h=1;≤(d)/(8)+2if h=2,3,4,5,6,7,8;≤(d)/(8)+1otherwise,for d=8(2k-1)+h, where k≥1 and 1≤h≤16.