Generalized de Bruijn multigraphs of rank \(\overarrow k\) (Q2713646)

Let \(A\) be a finite alphabet and \(V=A^{k_1}\times \cdots \times A^{k_m}\) for some positive integers \(k=(k_1,\ldots ,k_m)\). Let \(t\in V\) and \(a\in (A\cup \{*\})^m\), where \(*\not \in A\) and not all coordinates of \(a\) are \(*\). Elements \(t\) and \(a\) define uniquely a \(u\in V\): \(u_i=t_i\) if \(a_i=*\), else \(u_i\) arises from \(t_i\) by deleting the first term of \(t_i\in A^{k_i}\) and appending \(a_i\) to the end. A directed multigraph \(\text{GBG}_k=(V,E)\) is defined by putting in \(E\) all edges \((t,u)\) for all \(a\); \((t,u)\) is labelled by the corresponding \(a\). The \(\text{GBG}_k\) generalize the classical de Bruijn graphs (\(m=1\)). By a reduction to them it is shown that the \(\text{GBG}_k\) are connected, Eulerian, and Hamiltonian. An algorithm is presented for finding spanning subgraphs whose components are cycles.