Bijections in de Bruijn graphs.

zbMATH Open1463.05229arXiv1702.06906MaRDI QIDQ5206403FDOQ5206403

Authors: Josef Rukavicka 

Publication date: 18 December 2019

Abstract: A T-net of order $m$ is a graph with $m$ nodes and $2m$ directed edges, where every node has indegree and outdegree equal to $2$. (A well known example of T-nets are de Bruijn graphs.) Given a T-net $N$ of order $m$, there is the so called "doubling" process that creates a T-net $N^{*}$ from $N$ with $2m$ nodes and $4m$ edges. Let $|X|$ denote the number of Eulerian cycles in a graph $X$. It is known that $|N^{\ast }|=2^{m-1}|N|$. In this paper we present a new proof of this identity. Moreover we prove that $|N|leq{2}^{m-1}$. Let $Theta(X)$ denote the set of all Eulerian cycles in a graph $X$ and $S(n)$ the set of all binary sequences of length $n$. Exploiting the new proof we construct a bijection $Theta(N)imesS(m-1)ightarrowTheta(N^{\ast })$, which allows us to solve one of Stanley's open questions: we find a bijection between de Bruijn sequences of order $n$ and $S(2^{n-1})$.

Full work available at URL: https://arxiv.org/abs/1702.06906

Recommendations

• scientific article; zbMATH DE number 1890156
• A bijective proof of a theorem of Knuth
• On Leaf Node Edge Switchings in Spanning Trees of De Bruijn Graphs
• On extending de Bruijn sequences
• On the classification of deBruijn sequences

zbMATH Keywords

de Bruijn sequencebijectionde Bruijn graphT-net

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cited In (2)

• Bidirectional Variable-Order de Bruijn Graphs
• A bijective proof of a theorem of Knuth

This page was built for publication: Bijections in de Bruijn graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206403)