变更图的直径

P(t,n)和C(t,n)分别表示在阶为n的路和圈中添加t条边后得到的图的最小直径；f(t,k)表示从直径为k的图中删去t条边后得到的连通图的最大直径．这篇文章证明了t≥4且n≥5时,P(t,n)≤(n-8)/(t 1) 3；若t为奇数,则C(t,n)≤(n-8)/(t 1) 3；若t为偶数,则C(t,n)≤(n-7)/(t 2) 3．特别地,「(n-1)/5」≤P(4,n)≤「(n 3)/5」,「n/4」-1≤C(3,n)≤「n/4」．最后,证明了：若k≥3且为奇数,则f(t,k)≥(t 1)k-2t 4．这些改进了某些已知结果．

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 $tgeq4$ and $ngeq5$, $ P(t,n)leqfrac{n-8}{t+1}+3$, $C(t,n)leq frac{n-8}{t+1}+3$ if $t$ is odd and $ C(t,n)leq frac{n-7}{t+2}+3$ if $t$ is even; $leftlceilfrac{n-1}{5}rightrceilleq P(4,n)leqleftlceilfrac{n+3}{5}rightrceil$, $leftlceilfrac{n}{4}rightrceil-1leq C(3,n)leqleftlceilfrac{n}{4}rightrceil$; and $f(t,k)geq (t+1)k-2t+4$ if $kgeq 3$ and is odd, which improves some known results.