On arc‐traceable tournaments
Arthur H. Busch, Michael S. Jacobson, K. B. Reid · Journal of Graph Theory · 2006
Abstract A digraph D = (V, A) is arc‐traceable if for each arc xy in A, xy lies on a directed path containing all the vertices of V, that is, a hamiltonian path. Given a tournament T, it is well known that it contains a directed hamiltonian path. In this article, we develop the structure necessary for a tournament T to contain an arc xy that is not on any hamiltonian path. Using this structure, we give sufficient conditions for a tournament to be arc‐traceable. In addition, we give examples to show that these conditions are best possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 157–166, 2006