图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比de Bruijn网络有更好的限制边连通性.     

扩展de Bruijn图的生成树和广播

扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为[log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.     

一类不可约多项式的邻接矩阵

Dong和Pei在文[Construction for de Bruijn sequences with large stage,Des.Codes Cryptogr,2017,85(2):343-358]中利用F_2[x]的n次不可约多项式构造大级数de Bruijn序列.不可约多项式的邻接矩阵从理论上给出了这种方法能构造de Bruijn序列的数目.我们给出一类特殊不可约多项式的邻接矩阵,从理论上给出了用这类不可约多项式能够构造的de Bruijn序列的数目.     

二元稳定网络的算法及模型

通过建立JW(Jackson-Wolinsky)规则之下二元稳定网络的等价条件, 给出其完整算法. 引入边支付后, 证明了增连接情形具有边支付的二元稳定网络集合是二元稳定网络集合与具有边支付的二元稳定网络集合的交集. 考察两个特定的网络模型, 系统分析了它们的二元稳定性.     

一种生成k元de Bruijn序列的算法

目前,已有很多生成全长的移位寄存器序列(又称de Bruijn序列)的方法,他们的共同思想是先通过某种简单的移位寄存器生成所有不同的圈,然后再把它们联接为一个全长圈。在这篇文章中,我们先定义一个项链的周期约化,进而提出一种新的生成任意k元de Bruijn序列的方法。这种方法把这类算法从域推广到整数模上,而且在n≥3和k≥4时,这种算法能生成一大批de Bruijn序列。     

n维有向de Bruijn图和无向de Bruijn图上的随机游动

本文对有向和无向de Bruijn图上的随机游动进行了研究，得出了有向de Bruijn图上简单随机游动任意两点之间平均击中时间的显式表达式，并证明了有向和无向de Bruijn图上随机游动的快速收敛性。     

产生2元de Bruijn序列的一个新算法

de Bruijn序列是一类最长的非线性伪随机序列。本文给出了2元de Bruijn序列的一种新的生成算法,该算法能产生2~(δ·N(n,s))个n级de Bruijn序列,其中,0≤s≤2 (n-7)/2;当2~(l-1)相似文献   

n重线有向图的超连通性

本文证明了，在最小度至少为3的前提下超弧连通有向图的迭代线图是超点连通的．作为推论，我们得到了Kautz网络和de Bruijn网络的超点连通性和超弧连通性．     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

m阵列与M阵列的构作

给定正整数 m,n,r,s(1≤m≤r,1≤n≤s),A=(α_(ij))是 r×s 周期二元方阵.如果每个非零 m×n(二元)矩阵都是 A 的一个 m×n 子方阵,A 便叫做一个(r,s;m,n)-m 阵列.如果每个 m×n(二元)矩阵都是 A 的一个 m×n 子方阵,A 便叫做一个(r,s;m,n)-M 阵列.这分别是极大长度序列(或称 m-序列)及 de Bruijn 序列(或称 M-序列)的二维推广.本文讨论 m 阵列与 M 阵列的构作方法,以及它们的性质和存在性问题.     

Large fault-tolerant interconnection networks

This paper deals with reliability and fault-tolerant properties of networks. We first survey general reliability properties of networks, in particular those concerning diameter vulnerability. Then we study in details reliability properties of some families of networks in particular de Bruijn and Kautz networks and their generalizations which appear as very good fault-tolerant networks.     

Bisecting de Bruijn and Kautz graphs

De Bruijn and Kautz graphs have been intensively studied as perspective interconnection networks of massively parallel computers. One of the crucial parameters of an interconnection network is its bisection width. It has an influence on both communication properties of the network and the algorithmic design. We prove optimal bounds on the edge and vertex bisection widths of the k-ary n-dimensional de Bruijn digraph. This generalizes known results for k = 2 and improves the upper bound for the vertex bisection width. We extend the method to prove optimal upper and lower bounds on the edge and vertex bisection widths of Kautz graphs.     

Hamiltonicity of large generalized de Bruijn cycles

In this article, we determine when the large generalized de Bruijn cycles are Hamiltonian. These digraphs have been introduced by Gómez, Padró and Pérennes as large interconnection networks with small diameter and they are a family of generalized cycles. They are Kronecker products of generalized de Bruijn digraphs and dicycles.     

A recursive construction of nonbinary de Bruijn sequences

This paper presents a method to find new de Bruijn sequences based on ones of lesser order. This is done by mapping a de Bruijn cycle to several vertex disjoint cycles in a de Bruijn digraph of higher order and then connecting these cycles into one full cycle. We present precise formulae for the locations where those cycles can be rejoined into one full cycle. We obtain an exponentially large class of distinct de Bruijn cycles. This method generalizes the Lempel construction of binary de Bruijn sequences as well as its efficient implementation by Annextein.     

On even factorizations and the chromatic index of the Kautz and de Bruijn digraphs

Motivated by the problem of designing large packet radio networks, we show that the Kautz and de Bruijn digraphs with in- and outdegree d have arc-chromatic index 2d. In order to do this, we introduce the concept of even 1-factorizations. An even 1-factor of a digraph is a spanning subgraph consisting of vertex disjoint loops and even cycles; an even 1-factorization is a partition of the arcs into even 1-factors. We prove that if a digraph admits an even 1-factorization, then so does its line digraph. (In fact, we show that the line digraph admits an even 1-factorization even under a weaker assumption discussed below.) As a consequence, we derive the above property of the Kautz and de Bruijn digraphs relevant to packet radio networks. © 1993 John Wiley & Sons, Inc.     

Construction for de Bruijn sequences with large stage

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of generating de Bruijn sequences has received considerable attention. In this paper, we provide a method for generating large state (such as \(n=128\)) de Bruijn sequences.     

Classification theorems for operators preserving zeros in a strip

We characterize all linear operators which preserve certain spaces of entire functions whose zeros lie in a closed strip. Necessary and sufficient conditions are obtained for the related problem with real entire functions, and some classical theorems of de Bruijn and Pólya are extended. Specifically, we reveal new differential operators which map real entire functions whose zeros lie in a strip to real entire functions whose zeros lie in a narrower strip; this is one of the properties that characterize a “strong universal factor” as defined by de Bruijn. Using elementary methods, we prove a theorem of de Bruijn and extend a theorem of de Bruijn and Ilieff which states a sufficient condition for a function to have a Fourier transform with only real zeros.