Bijections in de Bruijn graphs.

MaRDI QIDQ5206403zbMATH OpenFDO

Authors Josef Rukavicka

Publication date 18 December 2019

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

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)

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^{\ast }$ 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})$.

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

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)