Quasi-hamiltonicity: A series of necessary conditions for a digraph to be hamiltonian

We introduce new necessary conditions, k-quasi-hamiltonicity (0 less than o r equal to k less than or equal to n - 1), for a digraph of order n to be h amiltonian. Every (k + 1)-quasi-hamiltonian digraph is also k-quasi-hamilto nian we construct digraphs which are k-quasi-hamiltonian, but not (k + 1)-q uasi-hamiltonian. We design an algorithm that checks k-quasi-hamiltonicity of a given digraph with n vertices and m arcs in time O(nm(k)). We prove th at (n - 1)-quasi-hamiltonicity coincides with hamiltonicity and 1-quasi-ham iltonicity is equivalent to pseudo-hamiltonicity introduced (for undirected graphs) by L. Babel and G. J. Woeginger (1997, in Lecture Notes in Comput. Sci., Vol. 1335, pp. 38-51, Springer-Verlag, New York/Berlin). (C) 2000 Ac ademic Press.