Gutin, Gregory and Yeo, Anders (2000) Quasi-hamiltonicity: a series of necessary conditions for a digraph to be hamiltonian. Journal of Combinatorial Theory - Series B, 78 (2).
Full text access: Open
We introduce new necessary conditions, k-quasi-hamiltonicity (0kn−1), for a digraph of order n to be hamiltonian. Every (k+1)-quasi-hamiltonian digraph is also k-quasi-hamiltonian; we construct digraphs which are k-quasi-hamiltonian, but not (k+1)-quasi-hamiltonian. We design an algorithm that checks k-quasi-hamiltonicity of a given digraph with n vertices and m arcs in time O(nmk). We prove that (n−1)-quasi-hamiltonicity coincides with hamiltonicity and 1-quasi-hamiltonicity 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).
This is a Submitted version This version's date is: 2000 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/183fde02-4d8d-3d09-dce7-cec34b61e4e1/2/
Deposited by Research Information System (atira) on 24-May-2012 in Royal Holloway Research Online.Last modified on 24-May-2012