Finding Hamiltonian circuits in quasi-adjoint graphs Original Research Article

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718–729]. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in image, as well as a polynomial algorithm in image for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed.