The Hamiltonian property of generalized de Bruijn digraphs (Q1179462): Difference between revisions

Let \(G_ B(n,d)\) denote the digraph with \(n\) nodes \(0,1,\dots,n-1\) and \(nd\) arcs of the form \(\overrightarrow{ij}\) where \(j=di+r\) (mod \(n\)), \(0\leq i\leq n-1\), \(0\leq r\leq d-1\). The digraph \(G_ I(n,d)\) is defined similarly except that now \(j=d(n-1-i)+r\). The authors' main result is that if \(d\geq 3\) and \(gcd(n,d)=1\), then both \(G_ B(n,d)\) and \(G_ I(n,d)\) have Hamilton circuits. The results in this paper plus results known earlier settle the problem of determining which of these graphs wave Hamilton circuits.