Premium
Sufficient conditions for a digraph to be Hamiltonian
Author(s) -
BangJensen Jørgen,
Gutin Gregory,
Li Hao
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199606)22:2<181::aid-jgt9>3.0.co;2-j
Subject(s) - digraph , mathematics , combinatorics , hamiltonian (control theory) , hamiltonian path , discrete mathematics , graph , mathematical optimization
We describe a new type of sufficient condition for a digraph to be Hamiltonian. Conditions of this type combine local structure of the digraph with conditions on the degrees of nonadjacent vertices. The main difference from earlier conditions is that we do not require a degree condition on all pairs of nonadjacent vertices. Our results generalize the classical conditions by Ghouila‐Houri and Woodall. © 1996 John Wiley & Sons, Inc.