广义de Bruijn有向图和Kautz有向图的限制性弧连通度  

Restricted Arc-Connectivity of Generalized De Bruijn Digraphs and Kautz Digraphs

作　　者：张珺昊 孟吉翔[1] ZHANG Junhao;MENG Jixiang(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）》2020年第4期415-427,共13页Journal of Xinjiang University(Natural Science Edition)

基　　金：国家自然科学基金项目(11531011).

摘　　要：有向图的限制性弧连接度是测量互连网络容错性的重要参数.本文证明了对于直径k≥4和参数d≥4的广义de Bruijn有向图BG(n, d),它的限制性弧连通度是2d-2.对于直径k≥4和参数d≥4或者d≥3, k≥5, n和d的最大公约数g.c.d(n,d)≥2和n可以被d+1整除的广义Kautz有向图KG(n, d),它的限制性弧连通度为2d-2.作为结论, BG(n, d)和KG(n, d)的超限制性弧连通性可以直接得出.本文还证明了对于任意的强连通有向图D有λh(D)≤min{ξh(D),|V1|λ(D2),|V2|λ(D1)}.另外,对于直径k≥4,证明这两类有向图分别跟自己做笛卡尔积得到的有向图的限制性弧连通度分别是d≥3,λ2(BG(n, d)×BG(n, d))=4d-2;d≥2,λ2(KG(n, d)×KG(n, d))=4d-2.The restricted arc-connectivity of a digraph is an important parameter to measure fault-tolerance of interconnection networks.This paper determines that the restricted arc-connectivity of the de Bruijn digraph BG(n,d)is equal to 2d−2 for diameter k≥4 and d≥4,and the restricted arc-connectivity of Kautz digraph KG(n,d)is equal to 2d−2 for k≥4,d≥4 or d≥3,k≥5,g.c.d(n,d)≥2 and n is divisible by(d+1).As consequences,the super restricted arc-connectedness of BG(n,d)and KG(n,d)is obtained immediately.This paper shows thatλh(D)≤min{ξ^h(D),|V1|λ(D2),|V2|λ(D1)}.In particular,for diameter k≥4,it can be determined thatλ2(BG(n,d)×BG(n,d))=4d−2 for d≥3 andλ2(KG(n,d)×KG(n,d))=4d−2 for d≥2.

关 键 词：限制性弧连通度 超–λ2 de Bruijn有向图 Kautz有向图 

分 类 号：O157[理学—数学]