𝔖 Bobbio Scriptorium
✦   LIBER   ✦

2-Partition-Transitive Tournaments

✍ Scribed by Barry Guiduli; András Gyárfás; Stéphan Thomassé; Peter Weidl

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
326 KB
Volume
72
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Given a tournament score sequence s 1 s 2 } } } s n , we prove that there exists a tournament T on vertex set [1, 2, ..., n] such that the degree of any vertex i is s i and the subtournaments of T on both the even and the odd vertices are transitive in the given order. This means that i beats j whenever i< j and i# j (mod 2). For any score sequence, we give an algorithm to construct a tournament of the above form, i.e. it is transitive on evens and odds in the given order. This algorithm fixes half of the edges of the tournament and then is similar to the algorithm for constructing a tournament given its score sequence. Another consequence provides asymptotics for the maximum number of edges in score unavoidable digraphs. From a result of Ryser, it is possible to get from any tournament to this special tournament by a sequence of triangle reversals. We show that n 2 Â2 reversals are always enough and that in some cases (1&o(1)) n 2 Â32 are required. We also show that such a sequence of triangle reversals can be found in O(n 2 ) time.

📜 SIMILAR VOLUMES

Subdivisions of Transitive Tournaments
Subdivisions of Transitive Tournaments
✍ A.D. Scott 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 77 KB

We prove that, for r ≥ 2 and n ≥ n(r ), every directed graph with n vertices and more edges than the r -partite Turán graph T (r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations of T (r, n) induced by orderings of the ve

Transitive partitions in realizations of
Transitive partitions in realizations of tournament score sequences
✍ Arthur H. Busch; Guantao Chen; Michael S. Jacobson 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract A tournament is an oriented complete graph, and one containing no directed cycles is called __transitive__. A tournament __T__=(__V, A__) is called __m__‐__partition transitive__ if there is a partition such that the subtournaments induced by each __X__~__i__~ are all transitive, an

Transitive tournaments and self-compleme
Transitive tournaments and self-complementary graphs
✍ András Gyárfás 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB

## Abstract A simple proof is given for a result of Sali and Simonyi on self‐complementary graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 111–112, 2001

Simple tournaments and sharply transitiv
Simple tournaments and sharply transitive groups
✍ Wilfried Imrich; Jaroslav Nešetřil 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 486 KB

We prove that with the possible exception of total orders every tournament with sharply transitive group of automorphisms is simple.

Kings in k-partite tournaments
Kings in k-partite tournaments
✍ Vojislav Petrovic; Carsten Thomassen 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 124 KB

Petrovic, V. and C. Thomassen, Kings in k-partite tournaments, Discrete Mathematics 98 (1991) 237-238. We prove that every k-partite tournament with at most one vertex of in-degree zero contains a vertex from which each other vertex can be reached in at most four steps.