Classification of de Bruijn-based labeled digraphs

Labeled digraphs, thanks to their special properties, are widely used in modeling real-world problems. Starting from de Bruijn graphs, they were used, among others, in modeling communication networks, architecture of parallel computers, or-in the area of bioinformatics-DNA sequencing and assembly problems. One of their most important properties is polynomial-time solvability of the Hamiltonian cycle/path problem, which makes these graphs especially useful as computational models. The classification presented here shows relations between subclasses of labeled digraphs, such as de Bruijn graphs, DNA graphs and others, and their connection with adjoints and quasi-adjoint graphs. The most recently defined class of quasi-adjoint graphs has a widest applicability, since it contains as subclasses all the de Bruijn-based labeled digraphs considered in this paper. The current work can be treated as a support in choosing an appropriate combinatorial model, resulting in polynomial time solution of problems related to searching for the Hamiltonian cycle or path, which are strongly NP-hard in general.