完全对换网络的容错性

The Fault Tolerance of Complete-Transposition Networks

完全对换网络是基于Cayley图模型的一类重要互连网络。f CT(n,k)(或F CT(n,k))表示在n维完全对换网络CT n中,使每个(n-k)维子完全对换网络失灵的失灵边(或点)的最小数目。分别给出了当k=0,1,n-2,n-1和k=2,n为素数时,f CT(n,k)(或F CT(n,k))的精确值;当3≤k≤n-3时,给出了f CT(n,k)和f s(n,k)的关系,其中f S(n,k)是使星网络S n中所有子星网络S n-k失灵的失灵边的最小数目;最后提出一个猜想。

Complete-transposition networks are important Cayley graphs model in networks design. fcr（ n, k） （ resp. Fcr（n,k） ） is the minimum number of faulty links （ resp. nodes ） that make every （n-k）-dimensional sub-complete-transposition networks faulty in CTn under link （resp. node） fail-ure model. The exact value forfcr（ n ,k） （resp. Fcr（n,k） ） is determined when n is prime and k = 2, or k = 0,1, n - 2, n - 1. For 3 ≤ k ≤ n - 3. The relationship between fcr（ n, k） and fs （ n, k） is presen-ted. f, （n, k） is the minimum number of faulty links that make every （n-k）-dimensional sub-star graph network faulty in Sn under link failure model. At last, the conjecture is proposed.