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.     

Embedding tournaments in simple tournaments

A tournament is simple if the corresponding relational system is simple in the algebraic sense. It is shown that any tournament T_n with n nodes can be embedded in a simple tournament T_n+1 apart from two exceptional types of tournaments which can be embedded in a simple tournament T_n+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.     

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.     

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.     

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.     

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.     

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     

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.     

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     

Upsets in round robin tournaments

LetT(R) be the class of tournaments having monotone score vectorR = (r₁,…, r_n). For a givenn, upper and lower bounds are given for the minimum number and maximum number of upsets for tournaments inT(R) withR strong. The cases of equality are characterized.     

Vertex-disjoint cycles in local tournaments

Let $r$ be a positive integer. The Bermond–Thomassen conjecture states that, a digraph of minimum out-degree at least $2r-1$ contains $r$ vertex-disjoint directed cycles. A digraph $D$ is called a local tournament if for every vertex $x$ of $D$, both the out-neighbours and the in-neighbours of $x$ induce tournaments. Note that tournaments form the subclass of local tournaments. In this paper, we verify that the Bermond–Thomassen conjecture holds for local tournaments. In particular, we prove that every local tournament $D$ with ${\delta }^{+}\left(D\right)\ge 2r-1$ contains $r$ disjoint cycles $C_1,C_2,\dots ,C_r$, satisfying that either $C_i$ has the length at most 4 or is a shortest cycle of the original digraph of $D-C_1-\dots -C_{i-1}$ for $1\le i\le r$.     

Universal arcs in local tournaments

An arc $uv$ of a digraph $D$ is called universal if $uv$ and $w$ are in a common cycle for any vertex $w$ of $D$. In this paper we characterize local tournaments whose every arc is universal.