Geodesic
On a conjecture of quintas and arc-traceability in upset tournaments
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 225-239.

Voir la notice de l'article provenant de la source Library of Science

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, i.e., hamiltonian path. We prove a conjecture of Quintas [7]: if D is arc-traceable, then the condensation of D is a directed path. We show that the converse of this conjecture is false by providing an example of an upset tournament which is not arc-traceable. We then give a characterization for upset tournaments in terms of their score sequences, characterize which arcs of an upset tournament lie on a hamiltonian path, and deduce a characterization of arc-traceable upset tournaments.
Keywords: tournament, upset tournament, traceable 
@article{DMGT_2005_25_3_a1,
     author = {Busch, Arthur and Jacobson, Michael and Reid, K.},
     title = {On a conjecture of quintas and arc-traceability in upset tournaments},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {225--239},
     publisher = {mathdoc},
     volume = {25},
     number = {3},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a1/}
}
TY  - JOUR
AU  - Busch, Arthur
AU  - Jacobson, Michael
AU  - Reid, K.
TI  - On a conjecture of quintas and arc-traceability in upset tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 225
EP  - 239
VL  - 25
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a1/
LA  - en
ID  - DMGT_2005_25_3_a1
ER  - 
%0 Journal Article
%A Busch, Arthur
%A Jacobson, Michael
%A Reid, K.
%T On a conjecture of quintas and arc-traceability in upset tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 225-239
%V 25
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a1/
%G en
%F DMGT_2005_25_3_a1
Busch, Arthur; Jacobson, Michael; Reid, K. On a conjecture of quintas and arc-traceability in upset tournaments. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 225-239. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a1/

[1] K.T. Balińska, M.L. Gargano and L.V. Quintas, An edge partition problem concerning Hamilton paths, Congr. Numer. 152 (2001) 45-54.

[2] K.T. Balińska, K.T. Zwierzyński, M.L. Gargano and L.V. Quintas, Graphs with non-traceable edges, Computer Science Center Report No. 485, The Technical University of Poznań (2002).

[3] K.T. Balińska, K.T. Zwierzyński, M.L. Gargano and L.V. Quintas, Extremal size problems for graphs with non-traceable edges, Congr. Numer. 162 (2003) 59-64.

[4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, Berlin, 2001).

[5] R.A. Brualdi and Q. Li, The interchange graph of tournaments with the same score vector, in: Progress in graph theory, Proceedings of the conference on combinatorics held at the University of Waterloo, J.A. Bondy and U.S.R. Murty editors (Academic Press, Toronto, 1982), 129-151.

[6] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).

[7] L.V. Quintas, private communication, (2001).

[8] L. Rédei, Ein Kombinatorischer Satz, Acta Litt. Szeged. 7 (1934) 39-43.

[9] K.B. Reid, Tournaments, in: The Handbook of Graph Theory, Jonathan Gross and Jay Yellen editors (CRC Press, Boca Raton, 2004).