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

On Fault-Tolerant Diameter And Wide Diameter Of 4-Connected Graphs

容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk,不超过宽直径dk.本文证明:当G是4连通图时,若D3=2,d4≤{D4+1,8D4?17};若D3≥3,d4≤max{3D2(3D4?D2?13)+1,2D2D3(D4?2)+D2?D2+1,3D2(D3?1)(D4?2)?D2?D2+1}12332并2222且证明对n(n≥3)连通图,当Dn=2时,2≤dn≤3.

Fault-tolerant diameter Dk and wide diameter dk are two important parameters for measuring reliability and efficiency of an interconnection network. It is clear Dk does not exceed dk for any k-connected graph. This paper shows that d4 ≤{D4 +1,8D4 ?17}if D3 =2 and d4 ≤ max{3D2(3D4 ? D2 ?13) +1,2D2D3(D4 ? 2) + D2 ? D2 +1,3D2(D3 ?1)(D4 ? 2) ? D2 ? D2 +1} 1 2 3 3 2 2 2 2 2 when G is a 4-connected graph.Then this paper also prove that 2 ≤ dn ≤ 3 if Dn =2 when G is a n-connected graph.