有向Kautz图的超级限制弧连通性

Super restricted arc-connectivity of Kautz digraphs

限制边连通度是比传统的边连通度更精确的网络可靠性指标.限制边连通度在有向图中有4个推广,分别对应有向图的4种限制弧连通度.有向Kautz图可以作为多处理机系统的基础拓扑,是一类重要网络.证明了有向Kautz图K(d,n)的4种限制弧连通度都为2d-2,并且确定了对应的最小限制弧割的结构特征.

Restricted edge-connectivity is a more refined network reliability index than traditional edge-connectivity. There are four generalizations of restricted edge-connectivity to digraphs, which correspond to four kinds of restricted arc-connectivity. Kautz digraphs are a kind of important networks, which can be used as the basic topology of multiprocessor systems. In this paper, the four kinds of restricted arc-connectivity of Kautz digraphs are all proved to be 2d-2 and the structural characteristics of the corresponding minimum restricted arc-cuts are also illustrated.