Kautz图的限制边连通度

Restricted Edge-connectivity of Kautz Graphs

限制边连通度是对传统边连通度的推广 ,而且是计算机互连网络容错性的一个重要度量 .本文考虑两类重要的网络模型———Kautz有向图K(d ,n)和Kautz无向图UK(d ,n)的限制边连通度λ′,并得到如下结果 :除了λ′(K( 2 ,1) )不存在外 ,均有λ′(K(d ,n) ) =2d-2 ;当d≥ 3 ,n≥ 3时 ,4d-5≤λ′(UK(d ,n) ) ≤ 4d -4 .

The restricted edge-connectivity is a generalization of classical edge-connectivity and can provide a more accurate measure of fault-tolerance for interconnection networks.In this paper,we consider restricted edge-connectivity λ′ of Kautz digraph K(d,n) and Kautz undirected graph UK(d,n),which are two classes of important network models.We obtain the following results:λ′(K(d,n))=2d-2 except λ′(K(2,1)),which does not exist,and 4d-5≤λ′(UK(d,n))≤4d-4 for d≥3 and n≥3.