PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2005 | 25 | 3 | 225-239
Tytuł artykułu

On a conjecture of quintas and arc-traceability in upset tournaments

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
25
Numer
3
Strony
225-239
Opis fizyczny
Daty
wydano
2005
otrzymano
2004-03-24
poprawiono
2005-01-13
Twórcy
  • Department of Mathematics, University of Colorado at Denver, Denver, CO 80217, USA
  • Department of Mathematics, University of Colorado at Denver, Denver, CO 80217, USA
  • Department of Mathematics, California State University San Marcos, San Marcos, CA 92096, USA
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1287
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.