Generalized de Bruijn Multigraphs of Rank

New class \(\mathcal{GBG}_{\overrightarrow{k}}\), of generalized de Bruijn multigraphs of rank \({\overrightarrow{k}}\in{N}^m\), is introduced and briefly characterized. It is shown, among the others, that every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\) is connected, Eulerian and Hamiltonian. Moreover, it consists of the subgraphs which are isomorphic with the de Bruijn graphs of rank \(r=\sum_{i=1}^{m} (d_1,\dots,d_m)\in\{0.1\}^m\). Then, the subgraphs of every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\), called the \({\overrightarrow{k}}\)-factors, are distinguished.

An algorithm, with small time and space complexities, for the construction of the \({\overrightarrow{k}}\)-factors, in particular the Hamiltonian circuits, is given. At the very end, a few open problems are put forward.