关于图的边添加(英文)  

On addition of edges of graphs

作　　者：胡青[1] 徐俊明[1] 

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

出　　处：《中国科学技术大学学报》2009年第3期229-232,264,共5页JUSTC

基　　金：Supported by NNSF of China(10671191).

摘　　要：给定任意正整数t和d(≥2),记P(t,d)为在直径d的路上加上t条边后所得图的最小直径.证明了:P(6,4)=1;当d=5,6,7时有P(6,d)=2;当d=7(2k-1)+h(k≥1,1≤h≤14)时有d7≤P(6,d)≤d7+2若h=7;d7+1其他;当d=5,6,7,8时有P(7,d)=2;当d=8(2k-1)+h(k≥1,1≤h≤16)时有d8≤P(7,d)≤d8若h=1;d8+2若h=2,3,4,5,6,7,8;d8+1其他.Given positive integers t and d （≥2）, let P （t, d） denote the minimum diameter of a graph obtained by adding t extra edges to a path with diameter d. It was proved that P（6,4）= 1, P（6,d）=2 for d=5,6,7, and [d/7]≤P（6,d）≤{[d/7]＋2 if h=7;[d/7]＋1 otherwise,for d=（2k-1）＋h,where k≥1 and 1≤h≤14.Moreover, P（7,d）=2 for d=5,6,7,8,and [d/8]≤P（7,d）{=[d/8] if h=1; ≤[d/8]＋2 if h=2,3,4,5,6,7,8;≤[d/8]＋1 otherwise, for d=8（2k-1）＋h,where k≥1 and 1≤h≤16.

关 键 词：直径 变更图 路 加边 最小直径 

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