PDF
Discussiones Mathematicae Graph Theory 25(3) (2005)
225-239
DOI: https://doi.org/10.7151/dmgt.1287
ON A CONJECTURE OF QUINTAS AND ARC-TRACEABILITY IN UPSET TOURNAMENTS
Arthur H. Busch and Michael S. Jacobson
Department of Mathematics
| K. Brooks Reid
Department of Mathematics
|
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, 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.
2000 Mathematics Subject Classification: 05C20, 05C45.
References
[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). |
Received 24 March 2004
Revised 13 January 2005
Close