A note on certain de Bruijn sequences with forbidden subsequences

We consider words over a finite alphabet with certain uniqueness properties (a subsequence of length k does not occur more than once) and distance properties (at least j other symbols separate the occurrence of the same symbol). The maximal length of these words is realised by linear de Bruijn sequences with certain forbidden subsequences. We prove the existence of these maximal sequences.     

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

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

Coordination through De Bruijn sequences

Let (x_t) be an n-periodic sequence in which the first n elements are drawn i.i.d. according to some rational distribution. We prove there exists a constant C such that whenever mlnm?Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.     

De Bruijn digraphs and affine transformations

Let be the additive group of 1×n row vectors over . For an n×n matrix T over  and , the affine transformation F_T,ω of sends x to xT+ω. Let α be the cyclic group generated by a vector . The affine transformation coset pseudo-digraph has the set of cosets of α in as vertices and there are c arcs from x+α to y+α if and only if the number of zx+α such that F_T,ω(z)y+α is c. We prove that the following statements are equivalent: (a)  is isomorphic to the d-nary (n−1)-dimensional De Bruijn digraph; (b) α is a cyclic vector for T; (c)  is primitive. This strengthens a result conjectured by C.M. Fiduccia and E.M. Jacobson [Universal multistage networks via linear permutations, in: Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, ACM Press, New York, 1991, pp. 380–389]. Under the further assumption that T is invertible we show that each component of is a conjunction of a cycle and a De Bruijn digraph, namely a generalized wrapped butterfly. Finally, we discuss the affine TCP digraph representations for a class of digraphs introduced by D. Coudert, A. Ferreira and S. Perennes [Isomorphisms of the De Bruijn digraph and free-space optical networks, Networks 40 (2002) 155–164].     

Practical algorithms to rank necklaces,Lyndon words,and de Bruijn sequences

We present practical algorithms for ranking k-ary necklaces and Lyndon words of length n. The algorithms are based on simple counting techniques. By repeatedly applying the ranking algorithms, both necklaces and Lyndon words can be efficiently unranked. Then, explicit details are given to rank and unrank the length n substrings of the lexicographically smallest de Bruijn sequence of order n.     

Independence number of de Bruijn graphs

In this paper, we give several exact values of the independence number of a de Bruijn graph UB(d,D) and in the other cases, we establish pertinent lower and upper bounds of this parameter. We show that asymptotically, if d is even, the ratio of the number of vertices of a greatest independent set of UB(d,D) is .     

Perfect matchings of a graph associated with a binary de Bruijn digraph

Let B_n be the binary de Bruijn digraph of order n and W the quotient set of the set of vertices of B_n with respect to the equivalence relation of rotation. Let G be the graph which has W as the set of vertices and in which two elements C and H are adjacent when there exist a vertex v of C and a vertex u of H such that (v,u) is an arc of B_n. Recently the problem of establishing whether the graph G has a perfect matching was posed. In this paper we answer in the positive to this problem in the case of n odd.     

Generalized de Bruijn Cycles

For a set of integers , we define a q-ary -cycle to be an assignment of the symbols 1 through q to the integers modulo q ⁿ so that every word appears on some translate of . This definition generalizes that of de Bruijn cycles, and opens up a multitude of questions. We address the existence of such cycles, discuss reduced cycles (ones in which the all-zeroes string need not appear), and provide general bounds on the shortest sequence which contains all words on some translate of . We also prove a variant on recent results concerning decompositions of complete graphs into cycles and employ it to resolve the case of completely.AMS Subject Classification: 94A55, 05C70.     

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     

The directed genus of the de Bruijn graph

Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph D_n is shown to be

     

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.     

Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems

A transition in a graph is defined as a pair of adjacent edges. A transition system of an Eulerian graph refers to a set of partitions such that for each vertex of the graph, there corresponds to a partition of the set of edges incident to the vertex into transitions. A generalized transition system $F\left(G\right)$ over a graph $G$ defines a set of transitions over $G$. A compatible Eulerian circuit of an Eulerian graph $G$ with a generalized transition system $F\left(G\right)$ is defined as an Eulerian circuit in which no two consecutive edges form a transition defined by $F\left(G\right)$. In this paper, we further introduce the concept of weakly generalized transition system which is an extension of the generalized transition system and prove some Ore-type sufficient conditions for the existence of compatible Eulerian circuits in Eulerian graphs with (weakly) generalized transition systems and obtain corresponding results for Eulerian digraphs. Our conditions improve some previous results due to Jackson and Isaak, respectively.     

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

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

An efficient shift rule for the prefer-max De Bruijn sequence

A shift rule for the prefer-max De Bruijn sequence is formulated, for all sequence orders, and over any finite alphabet. An efficient algorithm for this shift rule is presented, which has linear (in the sequence order) time and memory complexity.