关于3连通图的容错直径和宽直径  

On Fault-Tolerant Diameter and Wide Diameter of 3-Connected Graphs

作　　者：谢歆[1] 徐俊明[1] 

机构地区：[1]中国科学技术大学数学系

出　　处：《数学研究》2003年第3期293-296,共4页Journal of Mathematical Study

基　　金：国家自然科学基金(10271114);安徽省自然科学基金(01046102)

摘　　要：容错直径和宽直径是度量网络可靠性和有效性的重要参数。对任意k连通图,它的容错直径D_k不超过宽直径d_k。本文证明:当D_2=2时,d_3≤max{D_3+1,2D_3-2};当D_2≥3时,d_3≤(D_2-1)[2(D_2-1)(D_3-1)-D_2-2]+1。Fault-tolerant diameter Dk and wide diameter dk are two important parameters for measuring reliability and efficiency of an interconnection network. It is clear that Dk does not exceed dk for any k-connected graph. This paper shows that d3≤max{D3 + 1, 2D3 - 2} if D2 = 2 and d3≤(D2- 1)[2(D2- 1)(D3-1)-D2-2] + 1 if D2≥3.

关 键 词：3连通图 连通度 直径 容错直径 宽直径 网络 

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