Cycle-pancyclism in tournaments II

LetT be a Hamiltonian tournament withn vertices and a Hamiltonian cycle ofT. In this paper we develope a general method to find cycles of lengthk, n+4/2 < k < n, intersecting in a large number of arcs. In particular we can show that if there does not exist a cycle.C _k intersecting in at leastk – 3 arcs then for any arce of there exists a cycleC _k containinge and intersecting in at leastk – 2(n–3)/n–k+3 – 2 arcs. In a previous paper [3] the case of cycles of lengthk, k n+4/2 was studied.On leave at MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA.     

Cycle-pancyclism in tournaments I

LetT be a hamiltonian tournament withn vertices andγ a hamiltonian cycle ofT. In this paper we start the study of the following question: What is the maximum intersection withγ of a cycle of lengthk? This number is denotedf(n, k). We prove that fork in range, 3 ≤k ≤n + 4/2,f(n,k) ≥ k ? 3, and that the result is best possible; in fact, a characterization of the values ofn, k, for whichf(n, k) = k ? 3 is presented. In a forthcoming paper we studyf(n, k) for the case of cycles of lengthk > n + 4/2.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Weakening arcs in tournaments

A weakening arc of an irreducible tournament is an arc whose reversal creates a reducible tournament. We consider properties of such arcs and derive recurrence relations for enumerating strong tournaments with no such arcs, one or more such arcs, and exactly one such arc. We also give some asymptotic results on the numbers of such tournaments, among other things. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 142–162, 2004     

Disjoint paths in tournaments

Given k   pairs of vertices (_si,_ti)$(s_i,t_i)$(1≤i≤k)$(1\le i\le k)$ of a digraph G, how can we test whether there exist k   vertex-disjoint directed paths from _si$s_i$ to _ti$t_i$ for 1≤i≤k$1\le i\le k$? This is NP-complete in general digraphs, even for k=2$k=2$ [2], but for k=2$k=2$ there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.     

Cycles in bipartite tournaments

It is shown that if an oriented complete bipartite graph has a directed cycle of length 2n, then it has directed cycles of all smaller even lengths unless n is even and the 2n-cycle induces one special digraph.     

Unavoidable trees in tournaments

An oriented tree T on n vertices is unavoidable if every tournament on n vertices contains a copy of T. In this paper, we give a sufficient condition for T to be unavoidable, and use this to prove that almost all labeled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on vertices contains a copy of every oriented tree T on n vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft, and Osthus.     

Hamiltonian-connected tournaments

We characterize weakly Hamiltonian-connected tournaments and weakly panconnected tournaments completely and we apply these results to cycles and bypasses in tournaments with given irregularity, in particular, in regular and almost regular tournaments. We give a sufficient condition in terms of local and global connectivity for a Hamiltonian path with prescribed initial and terminal vertex. From this result we deduce that every 4-connected tournament is strongly Hamiltonian-connected and that every edge of a 3-connected tournament is contained in a Hamiltonian cycle of the tournament and we describe infinite families of tournaments demonstrating that these results are best possible.     

Quasi-random tournaments

We introduce a large class of tournament properties, all of which are shared by almost all random tournaments. These properties, which we term “quasi-random,” have the property that tournaments possessing any one of the properties must of necessity possess them all. In contrast to random tournaments, however, it is often very easy to verify that a particular family of tournaments satisfies one of the quasi-random properties, thereby giving explicit tournaments with “random-like” behavior. This paper continues an approach initiated in several earlier papers of the authors where analogous results for graphs (with R.M. Wilson) and hypergraphs are proved.     

Embedded antichains in tournaments

The maximum antichain cardinality (MACC) of a tournament is the maximum number of incomparable subtournaments of T. We establish some properties of MACC. We describe all tournaments whose MACC is 1 or 2, show that MACC can grow exponentially with the size of the vertex set of a tournament, and present some questions for further investigation.     

Star-factors of tournaments

Let S_m denote the m-vertex simple digraph formed by m − 1 edges with a common tail. Let f(m) denote the minimum n such that every n-vertex tournament has a spanning subgraph consisting of n/m disjoint copies of S_m. We prove that m lg m − m lg lg m ≤ f(m) ≤ 4m² − 6m for sufficiently large m. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 141–145, 1998     

Ranking participants in generalized tournaments

Consider the problem of ranking social alternatives based on the number of voters that prefer one alternative to the other. Or consider the problem of ranking chess players by their past performance. A wide variety of ranking methods have been proposed to deal with these problems. Using six independent axioms, we characterize the fair-bets ranking method proposed by Daniels [4] and Moon and Pullman [14].Received: January 2005     

Monochromatic paths in random tournaments

We prove that, with high probability, any 2‐edge‐coloring of a random tournament on n vertices contains a monochromatic path of length . This resolves a conjecture of Ben‐Eliezer, Krivelevich, and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.     

Endpoint extendable paths in tournaments

Let s(n) be the threshold for which each directed path of order smaller than s(n) is extendible from one of its endpoints in some tournament T_n It is shown that s(n) is asymptotic to 3n/4, with an error term at most 3 for infinitely many n. There are six tournaments with s(n) = n. © 1996 John Wiley & Sons, Inc.     

Note on eccentricities in tournaments

An (n - l)-tuple (b ₁...,b _n-i ) of nonnegative integers isb-realizable if there exists a tournamentT withn vertices such that for each k,1 ≤k ≤inn] ise-realizable if there exists a tournamentT with vertex setV(T) = {v ₁,…v _n } such thate _i is the eccentricity of v_i. In this note we characterizeb-realizable vectors ande-realizable sequences.     

Vertex-disjoint cycles in regular tournaments

The Bermond–Thomassen conjecture states for $r\ge 1$, any digraph of minimum out-degree at least $2r?1$ contains at least $r$ vertex-disjoint directed cycles. In a recent paper, Bessy, Sereni and the author proved that a regular tournament $T$ of degree $2r?1$ contains at least $r$ vertex-disjoint directed cycles, which shows that the above conjecture is true for regular tournaments. In this paper, we improve this result by proving that such a tournament contains at least $\frac{7}{6}r?\frac{7}{3}$ vertex-disjoint directed cycles.