On arc‐traceable tournaments | Zendy

Busch Arthur H. | Zendy; Jacobson Michael S. | Zendy; Reid K. B. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research