| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4650366 | Discrete Mathematics | 2008 | 14 Pages |
A digraph DD is arc-traceable if for every arc xyxy of DD, the arc xyxy belongs to a directed Hamiltonian path of DD. A local tournament is an oriented graph such that the negative neighborhood as well as the positive neighborhood of every vertex induces a tournament. It is well known that every tournament contains a directed Hamiltonian path and, in 1990, Bang-Jensen showed the same for connected local tournaments. In 2006, Busch, Jacobson and Reid studied the structure of tournaments that are not arc-traceable and consequently gave various sufficient conditions for tournaments to be arc-traceable. Inspired by the article of Busch, Jacobson and Reid, we develop in this paper the structure necessary for a local tournament to be not arc-traceable. Using this structure, we give sufficient conditions for a local tournament to be arc-traceable and we present examples showing that these conditions are best possible.
