Search

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.

We present a simple framework for constructing de Bruijn sequences, and more generally, universal cycles, via successor rules. The framework is based on the often used method of joining disjoint cycles. It generalizes four previously known de Bruijn sequence constructions and is applied to derive three new and simple de Bruijn sequence constructions. Four of the constructions apply the pure cycling register and three apply the complemented cycling register. The correctness of each new construction is easily proved using the new framework. Each of the three new de Bruijn sequence constructions can be generated in O ( n ) -time per bit using O ( n ) -space.

A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for posets, where lines are defined using the natural betweenness relation in posets. More precisely, we obtain a bound on the number of lines depending on the height of the poset. The extremal configurations are also determined. Finally, we introduce a new notion of lines in graphs and show that our result for posets can be extended to this setting.

A k -ary de Bruijn sequence of order n is a cyclic sequence of length k n in which each k -ary string of length n appears exactly once as a substring. A shift rule for a de Bruijn sequence of order n is a function that maps each length n substring to the next length n substring in the sequence. We present the first known shift rule for k -ary de Bruijn sequences that runs in O ( 1 ) -amortized time per symbol using O ( n ) space. Our rule generalizes the authors' recent shift rule for the binary case (A surprisingly simple de Bruijn sequence construction, Discrete Math. 339, 127-131).

We study how to generate binary de Bruijn sequences efficiently from the class of simple linear feedback shift registers with feedback function $f(x_0, x_1, \ldots, x_{n-1}) = x_0 + x_1 + x_{n-1}$ for $n \geq 3$, using the cycle joining method. Based on the properties of this class of LFSRs, we propose two new generic successor rules, each of which produces at least $2^{n-3}$ de Bruijn sequences. These two classes build upon a framework proposed by Gabric, Sawada, Williams and Wong in Discrete Mathematics vol. 341, no. 11, pp. 2977--2987, November 2018. Here we introduce new useful choices for the uniquely determined state in each cycle to devise valid successor rules. These choices significantly increase the number of de Bruijn sequences that can be generated. In each class, the next bit costs $O(n)$ time and $O(n)$ space for a fixed $n$., Comment: A basic implementation in C is included

We generalize Axel Thue’s familiar definition of overlaps in words, and observe that there are no infinite words avoiding split occurrences of these generalized overlaps. We give estimates for the length of the longest finite word that avoids split overlaps. Along the way we prove a useful theorem about repeated disjoint occurrences in words — an interesting natural variation on the classical de Bruijn sequences.

Pick any length n binary string b 1 b 2 ? b n and remove the first bit b 1 . If b 2 b 3 ? b n 1 is a necklace, then append the complement of b 1 to the end of the remaining string; otherwise append b 1 . By repeating this process, eventually all 2 n binary strings will be visited cyclically. This shift rule leads to a new de Bruijn sequence construction that can be generated in O ( 1 ) -amortized time per bit.

In a digraph G = ( V , A ) , a vertex u is said to dominate its out-neighbors v , that is, there is an arc ( u , v ) ? A . A set D ? V is a dominating set of G if each vertex of V ? D is dominated by some vertex of D . The domination number of G , denoted by γ ( G ) , is the minimum cardinality of a dominating set of G . Generalized de Bruijn digraphs G B ( n , d ) are good candidates for interconnection networks. Kikuchi and Shibata show that ? n d + 1 ? ? γ ( G B ( n , d ) ) ? ? n d ? . In this paper, by constructing a (consecutive) dominating set of a generalized de Bruijn digraph, we prove that its domination number has exactly two values, that is, γ ( G B ( n , d ) ) = ? n d + 1 ? or ? n d + 1 ? + 1 . Additionally, using a related result in number theory, we provide a complete characterization of generalized de Bruijn digraphs with the domination number equal to ? n d + 1 ? or ? n d + 1 ? + 1 . As a consequence of the above results, we prove a conjecture posed by Kikuchi and Shibata. The conjecture says that each generalized de Bruijn digraph has a minimum dominating set that is consecutive.

A twin dominating set in a digraph D = ( V , A ) is a set S ? V such that, for every w ? V ? S , there exist arcs ( u , w ) , ( w , v ) ? A with u , v ? S . A twin dominating set S is efficient if there is no arc in the subdigraph induced by S and, for every w ? V ? S , there exist exactly one vertex u ? S and exactly one vertex v ? S such that arcs ( u , w ) , ( w , v ) ? A . This paper resolves a conjecture regarding an efficient twin domination set in generalized De Bruijn digraphs. The conjecture says that the generalized De Bruijn digraphs G B ( n , d ) with n a multiple of d + 1 have an efficient twin dominating set if and only if d is even and relatively prime to n . This paper affirms this conjecture.

For a digraph G, a k-tuple twin dominating setD of G for some fixed k>=1 is a set of vertices such that every vertex is adjacent to at least k vertices in D, and also every vertex is adjacent from at least k vertices in D. If the subgraph of G induced by D is strongly connected, then D is called a connected k-tuple twin dominating set of G. In this paper, we give constructions of minimal connected k-tuple twin dominating sets for de Bruijn digraphs and Kautz digraphs.

Open problems arising from the Workshop on Generalizations of de Bruijn cycles and Gray Codes at the Banff International Research Station in December, 2004.

In 1992 Chung, Diaconis and Graham generalized de Bruijn cycles to other combinatorial families with universal cycles. Universal cycles have been investigated for permutations, partitions, k-partitions and k-subsets. In 1990 Hurlbert proved that there exists at least one Ucycle of n-1-partitions of an n-set when n is odd and conjectured that when n is even, they do not exist. Herein we prove Hurlbert's conjecture by establishing algebraic necessary and sufficient conditions for the existence of these Ucycles. We enumerate all such Ucycles for [email protected]?13 and give a lower bound on the total number for all n. Additionally we give ranking and unranking formulae. Finally we discuss the structures of the various solutions.

A vertex u in a digraph G out-dominates itself and all vertices v such that (u,v) is an arc of G, similarly, u in-dominates both itself and all vertices w such that (w,u) is an arc of G. A set D of vertices of G is a twin dominating set of G if every vertex of G is out-dominated by a vertex of D and in-dominated by a vertex in D. In this paper, we introduce the k-tuple twin domination in directed graphs. A set D of vertices of G is a k-tuple twin dominating set if every vertex of G is out-dominated by at least k vertices in D and in-dominated by at least k vertices in D. We consider the problem of the k-tuple twin domination in de Bruijn and Kautz digraphs, and give construction methods for constructing minimum k-tuple twin dominating sets in these digraphs.

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 12.

We study the distribution of the number of permutations with a given periodic up-down sequence w.r.t. the last entry, find exponential generating functions and prove asymptotic formulas for this distribution., 10 pages, 1 figure

A generalization of de Bruijn digraphs is defined for Parry's α-expansions and it is shown that the characteristic polynomial of these graphs is in principle that of α. With the help of this result we prove that certain functionals of α-expansions, e.g. the number of specific digital patterns, satisfy a central limit theorem, which is an extension of a result due to Drmota (Proceedings of the International Conference held in Graz, Austria, 1998, p. 103).

The concept of a consecutive-d digraph was proposed by Du, Hsu and Hwang as a generalization of de Bruijn digraphs, Kautz digraphs, and their generalizations given by Imase and Itoh and Reddy, Pradhan and Kuhl. In this paper, we determine the connectivity of consecutive-d digraphs and study how to modify consecutive-d digraphs to reach maximum connectivity. Our results will generalize and improve several existing results on the connectivity of de Bruijn digraphs, Kautz digraphs and Imase-Itoh digraphs.

A generalized p-cycle is a digraph whose set of vertices can be partitioned into p parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. Any digraph can be shown as a p-cycle with p = 1, and bipartite digraphs are generalized p-cycles with p = 2. A maximally connected digraph is said to be superconnected if every disconnecting set of δ vertices or edges is trivial, where δ stands for the minimum degree. In this work, we study the problem of disconnecting p-cycles by removing nontrivial subsets of vertices or edges. To be more precise, after obtaining optimal lower bounds for the parameters k1,λ1, that measure the superconnectivities, we present sufficient conditions for a p-cycle to be superconnected, and also sufficient conditions to guarantee optimum values of superconnectivities of a p-cycle. Finally, we apply our results to compute the superconnectivities of the family of De Bruijn generalized cycles.

A de Bruijn sequence of span n is a periodic sequence in which every n -tuple over the alphabet appears exactly once, starting within the minimal generating cycle of the sequence. The decoding problem for such a sequence is to determine the position of an arbitrary n -tuple over the alphabet. Algorithms that allow this problem to be solved efficiently are important in certain types of position sensing applications. We present constructions for de Bruijn sequences over a variety of alphabets, together with corresponding decoding algorithms, that constitute a significant improvement over existing methods. These results include a construction for binary de Bruijn sequences of arbitrary span whose decoding algorithm is both fast and storage-free.

In this paper, we present several relations among the Kronecker product, the line digraph operation, and isomorphic factorization. Using these relations, it is shown that a de Bruijn digraph B(d k ,D) has an isomorphic factorization into B(d,kD) . Then, we generalize this result to extended de Bruijn digraphs (the Kronecker product of de Bruijn digraphs).

In this note, first there are established simple formulas enabling the calculation of feedback functions that generate a cycle of given length over a given finite field. A theorem communicated in the appendix says that feedback functions producing cycles over a finite field can also be utilized for constructing general feedback functions yielding cycles (in particular, de Bruijn cycles) over an arbitrarily given finite alphabet.

The de Bruijn sequences of order n are divided into weight classes. In [4] the symmetry group for each of these weight classes was defined, and a method for determining it was given in the cases of minimal or maximal weight. In this paper we generalize this method to find a subgroup also in the cases of non-extremal weights. We conjecture that the subgroup is equal to the whole group.

The concept of a consecutive- d digraph was proposed by Du, Hsu and Hwang as a generalization of many digraphs, such as de Bruijn digraphs, Kautz digraphs, and Imase-Itoh digraphs, which contain many hamiltonian digraphs with near-minimum diameter and near-maximum connectivity. In this paper, we show sufficient conditions for modified consecutive- d digraphs to have super line-connectivity.

We use the cycle join algorithm to generate de Bruijn sequences from irreducible cyclic codes. The number of sequences obtained by this construction is related to the cyclotomic numbers. A bound for the number of sequences that can be constructed is given, and we investigate some cases where the cyclotomic numbers are explicitly known.

Let 5 be a family of subsets of an n-set, considered as a subposet of the Boolean algebra B.. Adjoin a minimum 0 and maximum i if necessary to form @. Let ~(95) denote the value of the Mdbius function p(6,i) in &. We compute the maximum value of Ip( as 9 ranges over three types of families in B,: lower order ideals, intervals of rank levels, and arbitrary rank-selections. The maxima are obtained by taking the lower half, the middle third, and every other rank of B,, respectively. The maximum for the first case was previously found by Eckhoff (1980) and Scheid (1979). It allows us to answer a question raised by Fiiredi based on his joint work with Chung, Graham and Seymour (1988). The third maximum was also previously given by Niven (1968) and de Bruijn (1970). Finally, we consider lower order ideal case for the lattice of subspaces of a vector space, the maximum being achieved by taking the whole poset.

Order n de Bruijn sequences are the period 2n binary sequences produced by an n stage feedback shift register. Properties of the number of sequences in the minimum and maximum weight classes of the generator functions are discussed.

Order n de Bruijn sequences are the period 2 n binary sequences produced by an n stage feedback shift register. Additional information is given on the weight class distribution for the order n =7 generator functions.

In this paper, we explore generalizations of de Bruijn cycles for a variety of families of combinatorial structures, including permutations, partitions and subsets of a finite set.

In this paper, we give the spectra and characteristic polynomials of generalized de Bruijn graphs. By Tutte's Theorem we can obtain the number of spanning trees and the number of Eulerian tours in such graphs.

A subset S of maximally independent vertices from the de Bruijn graph B n is a cover of B n if every vertex of B n − S is adjacent to some vector of S . We find bounds on the size of a cover and algorithms and constructions to achieve those bounds.

Let A be an m × n (0, 1)-matrix with row vectors R 1 ,…, R m and column vectors C 1 ,…, C n . If there exist integers α, β such that R i R j = α whenever R i ≠ R j and C i C j = β whenever C i ≠ C j , then A will be called geometric. ( R i R j , C i C j are the usual dot products of the vectors involved.) The geometric matrices are classified, and it is shown that (apart from certain trivialities) every geometric matrix is based on a symmetric balanced incomplete block design. Assume that each column of A has a zero entry and that C i ≠ C j for some i and j . Under these assumptions it is shown that m · min{R i R j :R i ≠R j }⩽n · max{C i C j :C i ≠C j } , and that equality occurs if and only if A is geometric. The results generalize a theorem of de Bruijn and Erdos concerning combinatorial designs.

In 1969 de Bruijn published a proof of the following fact: An a × ab × abc brick can be used to pack an A × B × C box if, and only if, the integers A , B , C are in some order a multiple of a , a multiple of ab , and a multiple of abc . We give a quick proof of this result based on the following elementary lemma. The polynomial ( x a - 1)( x ab - 1)( x abc - 1) divides ( x A - 1)( x B - 1)( x C - 1) if, and only if, the integers A , B , C are in some order a multiple of a , a multiple of ab , and a multiple of abc .

The cycle structure of the ''connection'' of feedback logics is applied to construct more polynomials which generate de Bruijn sequences.

A set of words {A 1 , A 2 , …, A t } can be independently prescribed if for every set of t nonnegative integers ν i ( i = 1, 2, …, t ), there exists a word S containing exactly ν i occurrences of A i ( i = 1, 2, …, t ). In this paper we consider n -letter sets of independently prescribable words, where an n -letter set is a set of n -letter words. We show that the maximum size for an independently prescribable n -letter set is q n − q n −1 , where q is the number of letters in the alphabet (assuming q > 2 or n > 2). An independently prescribable n -letter set J such that | J | = q n − q n −1 can be constructed in the following way: Let D be an ( n − 1)- de Bruijn sequence , a circular sequence with exactly one occurrence of every ( n − 1)-letter word froom a q -letter alphabet. Then an independently prescribable n -letter set with cardinality q n − q n −1 consists of all n -letter words except those occurring in D . We show that each de Bruijn sequence corresponds to a unique independently prescribable n -letter set J such that | J | = q n − q n −1 . If q > 2, the number of such sets is the number of ( n − 1)-de Bruijn sequences (( n , q ) ≠ (2, 3)). If q = 2 and n ⩾ 5, the number of such sets is 7 times the number of ( n − 1)-de Bruijn sequences. Some of the results in this paper are generalized in a theorem about independently prescribable sets of edges of Hamiltonian graphs.

This paper constructs a decreasing lexicographic list of necklaces of length n in beads of k colors. This list, somewhat modified, produces a k-ary de Bruijn sequence of length k n .

Let F be a family of m subsets (lines) of a set of n elements (points). Suppose that each pair of lines has λ points in common for some positive λ. The Nonuniform Fisher Inequality asserts that under these circumstances m ⩽ n. We examine the case when m = n. We give a short proof of the fact that (with the exception of a trivial case) such an F must behave like a geometry in the following sense: a line must pass through each pair of points. This generalizes a result of de Bruijn and Erdos.

An algebraic approach to enumerate the number of cycles of short length in the de Bruijn-Good graph G n is given and the following theorem is proved.

Let t>1, let P1,…,Pt be pairwise disjoint nonvoid subsets of a finite set P, and let L be a collection of subsets of P called lines. We say that (P 1 ,…,P t ; L ) is a colored incidence structure if (i) each line meets at least two blocks Pi and Pj, (ii) for arbitrary distinct xϵPi and yϵPj the pair {x, y} is a subset of exactly one line if i≠j and at most one line if i=j. Extending the work of de Bruijn and Erdos and Meshulam we show that for a coloured incidence structure (P 1 ,…,P t ; L ) with |P1|⩽…⩽|Pt| in general | L | exceeds 1+|P1|+…+ |Pt−1|. The exceptional cases are exactly: (i) | L |=|P 1 |+·+|P t−1 | if the structur e is a truncated projective plane and (ii) | L |=1+|P 1 |+·+∣P t−1 | holds in exactly six cases: a projective plane, the dual of an affine plane, the dual of a modification of an affine plane, a near-pencil, a structure with 2 lines and a 9-element structure with 7 lines.

De Bruijn cycles are cyclic binary strings of length n where all substrings of length i are distinct. We present a generalization called (≃, i )-De Bruijn cycles that are defined for an equivalence relation ≃ on substrings of length i. In this paper, binary (≃, i )-De Bruijn cycles under the equivalences of cyclic rotation, inverses, and flipping are examined. For the first two equivalences, we present exact solutions for all pairs ( i , n ) for which (≃, i )-De Bruijn cycles of length n exist; for the last equivalence a conjecture is made about which pairs hold.