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

张珺昊; 孟吉翔

doi:10.13568/j.cnki.651094.651316.2019.12.24.0001

您当前的位置：

首页 >

文章列表页 >

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

数理科学 | 更新时间：2026-01-21

- 广义deBruijn有向图和Kautz有向图的限制性弧连通度
- 广义deBruijn有向图和Kautz有向图的限制性弧连通度
- 新疆大学学报（自然科学版中英文） 2020年37卷第4期页码：415-427
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  国家自然科学基金项目(11531011)~~
- DOI：10.13568/j.cnki.651094.651316.2019.12.24.0001
  中图分类号： O157.5
- 纸质出版：2020
- 稿件说明：
移动端阅览
[1]张珺昊,孟吉翔.广义de Bruijn有向图和Kautz有向图的限制性弧连通度[J].新疆大学学报(自然科学版)(中英文),2020,37(04):415-427.
[1]张珺昊,孟吉翔.广义de Bruijn有向图和Kautz有向图的限制性弧连通度[J].新疆大学学报(自然科学版)(中英文),2020,37(04):415-427. DOI： 10.13568/j.cnki.651094.651316.2019.12.24.0001.

DOI：10.13568/j.cnki.651094.651316.2019.12.24.0001.

摘要

有向图的限制性弧连接度是测量互连网络容错性的重要参数.本文证明了对于直径k≥4和参数d≥4的广义de Bruijn有向图BG(n

它的限制性弧连通度是2d-2.对于直径k≥4和参数d≥4或者d≥3

k≥5

n和d的最大公约数g.c.d(n

d)≥2和n可以被d+1整除的广义Kautz有向图KG(n

它的限制性弧连通度为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.

Abstract

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.

关键词

Keywords

references

ZHU Y F,ZHANG Z.Restricted connectivity of line digraphs[J].Math Study,2010,43(2):107-113.

XU J M.Topological structure and analysis of interconnection networks[M].Dordrecht,Voston,London:Kluwer Academic Publishers,2001.

FAN Y M.Restricted edge-connectivity of a kind of Kautz graphs[J].Guangxi Normal Univ (Nat Sci Ed),2004,21:36-38.

OU J P,ZHANG F J.The super restricted edge-connectivity of graphs[J].Acta Math Sin,2004,47:931-940.

OU J P,CHENG X H,WU J C.On 3-restricted edge connectivity of undirected binary Kautz graphs[J].Discrete Math,2009,309:629-638.

WANG S Y,LIN S W.The maximal restricted edge connectivity of Kautz undirected graphs[J].Electron Notes Discrete Math,2005,22:49-53.

LI C F,LIN S W,LI S J.The restricted edge-connectivity of de Bruijn digraphs[J].Shanxi Univ,2006,29(2):131-133.

XU J M,L¨U M.Restricted edge-connectivity of de Bruijn digraphs[J].Hefei Univ,2008,87(1):385-392.

XU J M,L¨U M.On restricted arc-conectivity of regular digraphs[J].Taiwan Math,2005,9(4):661-670.

IMASE M,SONEOKA T,OKADA K.Connectivity of regular digraphs with small diameters[J].IEEE Trans Comput,1985,34:267-273.

CHEN X,LIU J.The restricted arc connectivity of Cartesian product digraphs[J].Inf Process Lett,2009,109:1202-1205.

VOLKMANN L.Restricted arc connectivity of digraphs[J].Inf Process Lett,2007,103:234-239.

LIN S W,JIN Y,LI C F.Cartesian product digraphs with optimal restricted arc connectivity[J].Inf Process Lett,2018,134:72-75.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据