Restricted Edge-connectivity of Kautz Graphs
Fan Ying-mei · Mathematica Applicata · 2004
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.