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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1287,
author = {Arthur H. Busch and Michael S. Jacobson and K. Brooks Reid},
title = {On a conjecture of quintas and arc-traceability in upset tournaments},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {225-239},
zbl = {1112.05045},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1287}
}
Arthur H. Busch; Michael S. Jacobson; K. Brooks Reid. On a conjecture of quintas and arc-traceability in upset tournaments. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 225-239. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1287/
[000] [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. | Zbl 0995.05089
[001] [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). | Zbl 1046.05038
[002] [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. | Zbl 1046.05038
[003] [4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, Berlin, 2001). | Zbl 0958.05002
[004] [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.
[005] [6] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). | Zbl 0541.05054
[006] [7] L.V. Quintas, private communication, (2001).
[007] [8] L. Rédei, Ein Kombinatorischer Satz, Acta Litt. Szeged. 7 (1934) 39-43.
[008] [9] K.B. Reid, Tournaments, in: The Handbook of Graph Theory, Jonathan Gross and Jay Yellen editors (CRC Press, Boca Raton, 2004).