(n,k)-排列图的条件连通度(英文)

Conditional Connectivity for(n,k)-arrangement Graphs

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R^l-连通度,记为k^l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k^l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.

Vertex connectivity is an important terconnection networks. Even though it reflects parameter to measure the fault tolerance of in- the fault tolerance correctly,, it undervalues the resilience of large networks. Conditional connectivity places some requirements on the components （when the network is destroyed） to overcome this shortcoming. Given a network based on a graph G and a positive integer l, the R1-connectivity of G, denoted by kl（G）, is the minimum cardinality of a set of vertices in G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least l. In this work, we establish that kl（An,k） = [（l ＋ 1）k - l]（n - k） - l for the （n, k）-arrangement graph An,k with k 〉1＋2 and n 〉 k ＋ l.