摘要
广义ｄｅＢｒｕｉｊｎ有向图ＧＩ（ｎ，ｄ）的顶点集为｛０，１，．．．，ｎ－１｝，弧集为ｉ→ｄ（ｎ－１－ｉ）＋ｒ（ｍｏｄｎ），０ｉｎ－１，０ｒｄ－１．本文证明：如果ＧＩ（ｎ，ｄ）的直径不小于５，那么它的连通度等于ｄ当且仅当ｇ．ｃ．ｄ．（ｎ，ｄ）２。
A generalized de Bruijn digraph G I(n,d) is such a digraph with the vertex set {0,1,2,…,n 1} and the arc set i→d(n-1-i)+r( mod n), 0in-1, 0rd-1. This paper presents the following result. If G I(n,d) has diameter at least five, then G I(n,d) has connectivity d if and only if g.c.d. (n,d)2 and d+1 divides n .
关键词
有向图
deBruijn有向图
广义
连通度
digraph, de Bruijn digraph, generalized de Bruijn digraphs, connectivity, interconnection network
