Extendable Cycles in Multipartite Tournaments

An n-partite tournament is an orientation of a complete n-partite graph. If D is a strongly connected n-partite (n3) tournament, then we shall prove that every partite set of D has at least one vertex which lies on a cycle C_m of each length m for such that V(C₃)V(C₄)V(C_n), where V(C_m) is the vertex set of C_m for . This result extends those of Bondy [2], Guo and Volkmann [4], Gutin [6], Moon [8], and Yeo [12].Final version received: June 9, 2003     

On the Number of 5‐Cycles in a Tournament

We find a formula for the number of directed 5‐cycles in a tournament in terms of its edge scores and use the formula to find upper and lower bounds on the number of 5‐cycles in any n‐tournament. In particular, we show that the maximum number of 5‐cycles is asymptotically equal to , the expected number 5‐cycles in a random tournament (), with equality (up to order of magnitude) for almost all tournaments.     

Quasi‐carousel tournaments

A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W₄ and L₄, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments  with  is called almost balanced if all but  vertices of  have outdegree . In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W₄ and L₄ in  goes to zero as n goes to infinity.     

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$.     

On multipartite posets

A poset P=(X,) is m-partite if X has a partition X=X₁X_m such that (1) each X_i forms an antichain in P, and (2) xy implies xX_i and yX_j where i<j. In this article we derive a tight asymptotic upper bound on the order dimension of m-partite posets in terms of m and their bipartite sub-posets in a constructive and elementary way.     

General frame constructions for Z-cyclic triplewhist tournaments

Frames are useful in dealing with resolvable designs such as resolvable balanced incomplete block designs and triplewhist tournaments. Z-cyclic triplewhist tournament frames are also useful in the constructions of Z-cyclic triplewhist tournaments. In this paper, the concept of an (h₁,h₂,…,hn;u)-regular Z-cyclic triplewhist tournament frame is defined, and used to establish several quite general recursive constructions for Z-cyclic triplewhist tournaments. As corollaries, we are able to unify many known constructions for Z-cyclic triplewhist tournaments. As an application, some new Z-cyclic triplewhist tournament frames and Z-cyclic triplewhist tournaments are obtained. The known existence results of such designs are then extended.     

Reconstructible and Half-Reconstructible Tournaments: Application to Their Groups of Hemimorphisms

Let T and T¹ be tournaments with n elements, E a basis for T, E′ a basis for T′, and k ≥ 3 an integer. The dual of T is the tournament T” of basis E defined by T(x, y) = T(y, x) for all x, y ε E. A hemimorphism from T onto T′ is an isomorphism from T onto T” or onto T. A k-hemimorphism from T onto T′ is a bijection f from E to E′ such that for any subset X of E of order k the restrictions T/X and T¹/f(X) are hemimorphic. The set of hemimorphisms of T onto itself has group structure, this group is called the group of hemimorphisms of T. In this work, we study the restrictions to n – 2 elements of a tournament with n elements. In particular, we prove: Let k ≥ 3 be an integer, T a tournament with n elements, where n ≥ k + 5. Then the following statements are equivalent: (i) All restrictions of T to subsets with n – 2 elements are k-hemimorphic. (ii) All restrictions of T to subsets with n – 2 elements are 3-hemimorphic. (iii) All restrictions of T to subsets with n – 2 elements are hemimorphic. (iv) All restrictions of T to subsets with n – 2 elements are isomorphic, (v) Either T is a strict total order, or the group of hemimorphisms of T is 2-homogeneous.     

Componentwise complementary cycles in multipartite tournaments

The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n ≥ 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Let D be a 2-strong n-partite (n ≥ 6) tournament that is not a tournament. Let C be a 3-cycle of D and D \ V (C) be nonstrong. For the unique acyclic sequence D1, D2, ··· , Dα of D \V (C), where α≥ 2, let Dc = {Di|Di contains cycles, i = 1, 2, ··· , α}, Dc = {D1, D2, ··· , Dα} \ Dc. If Dc ≠ , then D contains a pair of componentwise complementary cycles.