关于图的边添加和减少

用P（t，d）（或者C（t，d））表示从长为d的路（或者圈）通过添加t条边后得到的图的最小直径，Tp（p，d）（或者Tc（p，d））表示为了得到直径最多为p的图需要向长为d的路（或者圈）中添加的最少边数，f（t，d）表示从直径为d的图中删去t条边后得到的连通图的最大直径．我们给出了这些参数新的上下界．特别地，证明了GrigorescuJ．Graph Theory，2003，43（2）：299—303]猜想：Tc（3，d）=d-8，其中d≥12；并且部分地解决了Schoone等人J．Graph Theory，1987，11（13）：409—427]的猜想：f（t，d）≤（t＋1）d-t＋1．

On addition and deletion of edges of graphs

Let P(t,d) (resp. C(t,d)) denote the minimum diameter of a graph obtained by adding t extra edges to a path (resp. cycle) of length d. Let TP(p,d) (resp. TC(p,d)) be the minimum number of edges added to a path (resp. cycle) of length d in order to obtain a graph of diameter not greater than p. Let f(t,d) denote the maximum diameter of a connected graph obtained after deleting t edges from a connected graph of diameter d. Some new lower and upper bounds of these parameters were presented. In particular, it is proved that TC(3,d)=d-8 for d≥12 conjectured by Grigorescu J. Graph Theory, 2003,43(2):299-303], and it is partially proved that f(t,d)≤(t+1)d-t+1 conjectured by Schoone et al J. Graph Theory, 1987,11(3):409-427].