正则图的宽直径(英文)  

The wide-diameter of regular graphs

作　　者：李佳傲[1,2] 徐俊明[1,2] 

机构地区：[1]中国科学技术大学数学科学学院 [2]中国科学院吴文俊数学重点实验室,安徽合肥230026

出　　处：《中国科学技术大学学报》2013年第8期603-606,共4页JUSTC

基　　金：Supported by NNSF of China(61272008)

摘　　要：宽度为m的图G的直径是最小整数d,使得G中任何两顶点之间至少存在m条其长度都不超过d的内点不交的路.对于任何满足[(2w+5)/3]≤m≤w的整数m,给出了n阶w正则w连通图的m宽直径的上界为[((n-2)(w-2))/((w-m+1)(3m-w-4))]+1.它能导出和改进某些已知结果.The diameter with width m of a graph G is defined as the minimum integer d for which between any two distinct vertices in G there exist at least m internally disjoint paths of length of at most d. It was shown that the tight upper bound on m-diameter of w-regular w-connected graph with order n is ＂（n-2）（w-2）/（w-m＋1）（3m＋w-4）＂＋1 for any integer m with ＂2w＋5/3＂≤m≤w.Some known results can be deduced or improved from the obtained result.

关 键 词：图论 连通度 直径 宽直径 正则图 网络 容错性 

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