链状正则图的平均距离

• 作 者: 何文杰 李双虎
• 机 构: 河北省科学院,河北省科学院石家庄050081,石家庄050081
• 出 处: 应用数学
• 发表日期: 1991年2期
• 关键词: 链状 正则图 平均距离 直径 距离 Distance Average distance Chain regular graph Diameter

本文构造了一类链状正则图G_k∶δ,求出了它们的平均距离D(G_k.δ),并得到关系式上式等号成立当且仅当δ=4f且k=0.这个估计式指出了施容华猜想[1]D(G)≤n/(δ+1)不成立. 文中进一步证明了这一类链状正则图有最大的直径,所以可以作出猜想: 若G是n阶连通图,则D(G)<(n+1)/(δ+1),其中δ是图G的最小度。