Perfect factors in the de Bruijn graph (Q1345135)

The \(c\)-ary \(u\)-th order de Bruijn graph, denoted \(G_{u,c}\), is defined to be the digraph whose vertices are the \(u\)-tuples of elements of an alphabet \(A\), \(| A|= c\), with an arc from vertex \((x_ 1,\dots, x_ u)\) to vertex \((y_ 1,\dots, y_ u)\) if \(x_{i+ 1}= y_ i\) for \(i= 1,\dots, u-1\). A uniform directed 2-factor of \(G_{u,c}\) is a collection of vertex-disjoint directed cycles, all of the same length, such that each vertex lies on one of the directed cycles. A \(c\)-ary \((r,s; u,v)\) perfect map is an \(r\times s\) periodic array with elements from an alphabet \(A\), \(| A|= c\), with the property that each \(u\times v\) \(c\)-ary array arises once as a subarray in one period of the array. The author develops necessary conditions for the existence of uniform 2-factors in \(G_{u,c}\), shows that these conditions are sufficient in certain cases, and uses these results to obtain new non- binary perfect maps.