扩展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图的广播时间的上界.     

de Bruijn定理的推广

de Bruijn定理是一种重要的组合计数方法，本文以非常自然的方式推广了这种方法．p图是图G在其顶点上的置换群P作用下形成的轨道．文中引进了P-图，P-图的色容指标，P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念，建立了色权多项式的计算公式和一系列的组合公式及性质．     

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

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

二元de Bruijn网络的可靠性分析

证明了二元de Bruijn网络是极大限制边连通的,并且它们的最小限制边割只能分离一条孤立边或者一个三角形. 利用此结果分析了二元de Bruijn网络的可靠性,确定了它们的可靠多项式的前四项系数.     

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

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

广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比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有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

广义de Bruijn有向图的k-元控制集

$G=(V, A)$ 表示一个有向图, 其中 $V$ 和 $A$ 分别表示有向图 $G$ 的点集和弧集。 对集合 $D_{k}\subseteq V(G)$, 如果对于任意点 $v\in V(G)$, 都存在 $k$ 个点 $u_{i}$, $1\leq i\leq k$ (可能存在某个 $u_{i}$ 和 $v$ 是同一点) 使得 $(u_{i},v)\in A(G)$, 则称 $D_{k}$ 是 $G$ 的一个 $k$-元控制集。 有向图 $G$ 的 $k$-元控制数 $\gamma_{\times k}(G)$ 是 $G$ 的最小 $k$-元控制集所含点的数目。 给出了广义 de Bruijn 有向图的 $k$-元控制数的新上界, 并且具体给出了构造广义 de Bruijn 有向图的 $k$-元控制集的方法。 此外, 对某些特殊的广义 de Bruijn 有向图, 通过构造其 $k$-元控制集, 进一步改进了它们 $k$-元控制数的上界。     

de Bruijn图的(1,2)-步竞争图

设D=(V,A)是一个有向图.有向图D的(1,2)-步竞争图是关于V(D)的无向图,表示为C_(1,2)(D).若边{x,y}∈E(C_(1,2)(D)),当且仅当存在一个顶点z≠x,y,使得d_(D-y)(x,z)≤1且d_(D-x)(y,z)≤2或者d_(D-x)(y,z)≤1且d_(D-y)(x,z)≤2.在2000年,Cho等人给出了m-步竞争图的定义.主要研究了deBruijn图的(1,2)-步竞争图,并给出了deBruijn图中的弧为C_(1,2)(D)的边的一个刻画.     

A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants

The classification problem of endomorphisms of the Cuntz algebra O_N\mathcal{O}_{N} is solved by using graph theory. We introduce permutative de Bruijn graphs as generalizations of de Bruijn graphs. Branching laws for a permutative endomorphism ρ of O_N\mathcal{O}_{N} are computed by using the permutative de Bruijn graph associated with ρ. According to this correspondence between endomorphisms and graphs, we classify permutative endomorphisms of O_N\mathcal{O}_{N} by graph invariants concretely.     

On a generalized model of labeled graphs

Labeled graphs have applications in algorithms for reconstructing chains that have been split into smaller parts. Chain reconstruction is a common problem in biochemistry and bioinformatics, particularly for sequencing DNA or peptide chains. Labeled graphs (in the sense defined in this paper) have also the important structural property which allows to reduce the Hamiltonian path problem to Eulerian path problem. This work introduces a model and properties of a class of base-labeled graphs that unify the properties of labeled and free-labeled graphs (B?a?ewicz et al., 1999) [1]. It describes the basic relationships between those classes and some of their applications. It also introduces lexical graphs which are the superclass of de Bruijn graphs. Lexical graphs keep many properties of de Bruijn graphs which have a wide area of applications e.g. in mathematics, electronics and computing sciences.     

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.     

Reinforcement numbers of digraphs

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.     

Generalized de Bruijn graphs

Oriented graphs in which every pair of vertices can be connected by a unique path of given length (not depending on the choice of the pair of vertices) are studied. These graphs are a natural extension of the well-known de Bruijn graphs and retain their most important properties. Some results on the structure of and methods for constructing such graphs are obtained. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 540–548, October, 1997. Translated by O. V. Sipacheva     

Symbolic analysis of finite words: the complexity function

We present several properties of the complexity function of finite words, the function counting the number of different factors in a word, for each length. To establish a first set of properties, we use the de Bruijn graphs and the suffix tree representations of a word. This allows us to show some inequalities that control the variation as well as the maximal value of the complexity function. Motivated by the applications, we discuss the change of the complexity function when sliding or increasing the size of a window laid down on a sequence to be analysed.     

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.     

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.     

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.     

广义de Bruijn有向图及其叠线图的支撑树与欧拉环游的计数

给出了一类特殊的广义deBruijn有向图的支撑树与欧环游的数目的简洁表示式，并得到了广义deBruijn有向叠线图的支撑树与欧拉环境数目的计算公式。