On a conjecture of quintas and arc-traceability in upset tournaments
Arthur H. Busch; Michael S. Jacobson; K. Brooks Reid
Discussiones Mathematicae Graph Theory (2005)
- Volume: 25, Issue: 3, page 225-239
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topArthur H. Busch, Michael S. Jacobson, and K. Brooks Reid. "On a conjecture of quintas and arc-traceability in upset tournaments." Discussiones Mathematicae Graph Theory 25.3 (2005): 225-239. <http://eudml.org/doc/270331>.
@article{ArthurH2005,
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.},
author = {Arthur H. Busch, Michael S. Jacobson, K. Brooks Reid},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {tournament; upset tournament; traceable; arc-traceability; Hamiltonian path},
language = {eng},
number = {3},
pages = {225-239},
title = {On a conjecture of quintas and arc-traceability in upset tournaments},
url = {http://eudml.org/doc/270331},
volume = {25},
year = {2005},
}
TY - JOUR
AU - Arthur H. Busch
AU - Michael S. Jacobson
AU - K. Brooks Reid
TI - On a conjecture of quintas and arc-traceability in upset tournaments
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 225
EP - 239
AB - 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.
LA - eng
KW - tournament; upset tournament; traceable; arc-traceability; Hamiltonian path
UR - http://eudml.org/doc/270331
ER -
References
top- [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. Zbl0995.05089
- [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). Zbl1046.05038
- [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. Zbl1046.05038
- [4] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer-Verlag, Berlin, 2001). Zbl0958.05002
- [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). Zbl0541.05054
- [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).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.