Diameters of Altered Graphs  

变更图的直径(英文)

作　　者：吴叶舟[1] 徐俊明[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《Journal of Mathematical Research and Exposition》2006年第3期502-508,共7页数学研究与评论（英文版）

基　　金：the National Natural Science Foundation of China (10271114)

摘　　要：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.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．这些改进了某些已知结果．

关 键 词：DIAMETER altered graph edge addition edge deletion. 

分 类 号：O157.5[理学—数学]