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

On addition and deletion of edges of graphs

作　　者：NAJIM Alaa A 徐俊明[1] 

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

出　　处：《中国科学技术大学学报》2006年第9期951-955,共5页JUSTC

基　　金：Supported by NNSF of China (10271114)

摘　　要：用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.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 lengthd. Let Te（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].

关 键 词：直径 变更图 边添加 边减少 Schoone等的猜想 

分 类 号：O157.5[理学—数学] TP302.1[理学—基础数学]