Discussiones Mathematicae Graph Theory 25(3) (2005) 225-239

ON A CONJECTURE OF QUINTAS AND ARC-TRACEABILITY IN UPSET TOURNAMENTS

Arthur H. Busch and Michael S. Jacobson

Department of Mathematics
University of Colorado at Denver
Denver, CO 80217, USA

K. Brooks Reid

Department of Mathematics
California State University San Marcos
San Marcos, CA 92096, USA

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