Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs

DOI10.1016/0166-218X(92)90149-5zbMath0818.05040OpenAlexW2064077828MaRDI QIDQ1199445

Ueli M. Maurer

Publication date: 16 January 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90149-5

zbMATH Keywords

boundsnumber of cyclesde Bruijn-Good graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Enumeration in graph theory (05C30) Paths and cycles (05C38) Directed graphs (digraphs), tournaments (05C20)

Related Items

A generalization of de Bruijn graphs and classification of endomorphisms of Cuntz algebras by graph invariants, Random feedback shift registers and the limit distribution for largest cycle lengths, Graphs with the unique path property: Structure, cycles, factors, and constructions, Translation invariant extensions of finite volume measures, Maximal state complexity and generalized de Bruijn words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The enumeration of shift register sequences
• An Erdős-Rényi law with shifts
• Number theory in science and communication. With applications in cryptography, physics, digital information, computing, and self- similarity.
• On the complexities of de-Bruijn sequences
• A proof of Golomb's conjecture for the de Bruijn graph
• On extremal factors of the de Bruijn graph
• A Design for Directed Graphs with Minimum Diameter
• Generalized de Bruijn digraphs
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers
• Normal Recurring Decimals