Premium
On arc‐traceable tournaments
Author(s) -
Busch Arthur H.,
Jacobson Michael S.,
Reid K. B.
Publication year - 2006
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/jgt.20173
Subject(s) - tournament , digraph , hamiltonian path , arc (geometry) , mathematics , combinatorics , hamiltonian (control theory) , path (computing) , directed graph , graph , discrete mathematics , computer science , geometry , mathematical optimization , programming language
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