图的边添加和减少(英文)

用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].

关于图的边添加和减少(英文)

用P(t,d)(或者C(t,d))表示从长为d的路(或者圈)通过添加t条边后得到的图的最小直径,TP(p,d)(或者TC(p,d))表示为了得到直径最多为p的图需要向长为d的路(或者圈)中添加的最少边数,f(t,d)表示从直径为d的图中删去t条边后得到的连通图的最大直径.我们给出了这些参数新的上下界.特别地,证明了Grigorescu[J.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.

变更图的直径(英文)

对于给定的正整数 t和 d( 2 ) ,用 F(t,d)和 P(t,d)分别表示在所有直径为 d的图和路中添加 t条边后得到的图的最小直径 ,用 f (t,d)表示从所有直径为 d的图中删去 t条边后得到的图的最大直径 .已经证明 P(1 ,d) =d2 ,P(2 ,d) =d +13 和 P(3,d) =d +24 .一般地 ,当 t和 d 4时有 d +1t+1 - 1 P(t,d) d +1t+1 +3.在这篇文章中 ,我们得到 F(t,f (t,d) ) d f(t,F(t,d) )和 dt+1 F(t,d)= P(t,d) d - 2t+1 +3,而且当 d充分大时 ,F(t,d) dt +1 .特别地 ,对任意正整数 k有 P(t,(2 k-1 ) (t+1 ) +1 ) =2 k,当 t=4或 5,且 d 4时有 dt+1 P(t,d) dt+1

Diameters of Altered Graphs

Let P（t, n） and C（t, n） denote the minimum diameter of a connected graph obtained from a single path and a circle of order n plus t extra edges, respectively, and f（t, k） the maximum diameter of a connected graph obtained by deleting t edges from a graph with diameter k. This paper shows that for any integers t ≥4 and n ≥ 5, P（4, n） ≤n-8/t＋1＋ 3, C（t,n）≤n-8/t＋1＋3 if t is odd and C（t,n） ≤n-7/t＋2 ＋3 if t is even; [n-1/5] ≤P（4,n） ≤ [n＋3/5] [n/4]-1≤C（3,n）≤[n/4]; and f（t, k）≥ （t ＋ 1）k - 2t ＋ 4 if k≥3 and is Odd, which improves some known results.