正则图的宽直径

摘要

宽度为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.它能导出和改进某些已知结果.