On Disjoint Cycles of the Same Length in Tournaments

A tournament is an orientation of the complete graph. Tournaments form perhaps the most interesting class of digraphs and it has a great potential for application. Tournaments provide a model of the statistical technique called the method of paired comparisons and they have also been studied in connection with sociometric relations in small groups. In this paper, we investigate disjoint cycles of the same length in tournaments. In 2010, Lichiardopol conjectured that for given integers l ≥ 3 and ...     

Non‐Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d

Let T be a strong tournament of order with diameter . A vertex w in T is non‐critical if the subtournament is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most critical vertices. This fact and Moon's vertex‐pancyclic theorem imply that for , it contains at least circuits of length . We describe the class of all strong tournaments of order with diameter for which this lower bound is achieved and show that for , the minimum number of circuits of length in a tournament of this class is equal to . In turn, the minimum among all strong tournaments of order with diameter 2 grows exponentially with respect to n for any given . Finally, for , we select a strong tournament of order n with diameter d and conjecture that for any strong tournament T of order n whose diameter does not exceed d, the number of circuits of length ? in T is not less than that in for each possible ?. Moreover, if these two numbers are equal to each other for some given , where , then T is isomorphic to either or its converse . For , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case . In an Appendix, some problems concerning non‐critical vertices are considered for generalizations of tournaments.     

Maximum Arc-integrity of Tournaments and Bipartite Tournaments

In this paper we extend the graphical concept of edge-integrity to directed graphs. After some general results we focus on the maximum arc-integrity which can be obtained by orienting the edges of K_n and K_{m, n} for m ≤ 4.     

Finding Scores in Tournaments

A tournamentT_nis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek( ≤ (n − 1)/2) inT_nis Θ(nk). This bound is in sharp contrast to the Θ(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen − 1) in a directed graph.     

Claws in Rotational Tournaments

 A claw is a rooted tree whose each branch is a directed path starting at the root. We prove that each rotational tournament on 2n+1 vertices contains all claws with 2n edges and at most n branches. Received: December 15, 1999 Final version received: April 18, 2001 Acknowledgements. The authors wish to express their gratitude to the referee for valuable remarks, suggestions and comments that led to an improved paper.     

哈密尔顿多部竞赛图

本文证明了如下结果：设Ｔ为几乎正则ｎ－部竞赛图（ｎ　７）,则Ｔ必含哈密尔顿圈．     

Constructions Over Tournaments

We investigate tournaments that are projective in the variety that they generate, and free algebras over partial tournaments in that variety. We prove that the variety determined by three-variable equations of tournaments is not locally finite. We also construct infinitely many finite, pairwise incomparable simple tournaments.     

Subdivisions of Transitive Tournaments

We prove that, for r ≥ 2 andn ≥ 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 ofT (r, n) induced by orderings of the vertex classes.     

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     

Packing Triangles in Regular Tournaments

We prove that a regular tournament with n vertices has more than pairwise arc‐disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than , so these tournaments do not have pairwise arc‐disjoint triangles.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

Weighted Matching in Chess Tournaments

In many chess tournaments, e.g. when the Swiss system is used, the number of players is much larger than the number of rounds to be played. In such tournaments the pairing for a round depends on the results in earlier rounds, and the pairing process can be very complicated. In these pairing systems the main goals are to let players with equal scores play together, and that each player should alternately play white and black, with the restriction that no player may face the same opponent more than once. The paper describes how a weighted matching algorithm is used to find ‘the best pairing’ by converting the pairing rules into penalty points.     

On High-Dimensional Acyclic Tournaments

We study a high-dimensional analog for the notion of an acyclic (aka transitive) tournament. We give upper and lower bounds on the number of $d$ -dimensional $n$ -vertex acyclic tournaments. In addition, we prove that every $n$ -vertex $d$ -dimensional tournament contains an acyclic subtournament of $\Omega (\log ^{1/d}n)$ vertices and the bound is tight. This statement for tournaments (i.e., the case $d=1$ ) is a well-known fact. We indicate a connection between acyclic high-dimensional tournaments and Ramsey numbers of hypergraphs. We investigate as well the inter-relations among various other notions of acyclicity in high-dimensional tournaments. These include combinatorial, geometric and topological concepts.     

Groups of Automorphisms of Tournaments

By the Holland Representation Theorem, every lattice ordered group (l-group) is isomorphic to a subalgebra of the l-group of automorphisms of a chain. Since weakly associative lattice groups (wal-groups) and tournaments are non-transitive generalizations of l-groups and chains, respectively, the problem concerning the possibility of representation of wal-groups by automorphisms of tournaments arises. In the paper we describe the class of wal-groups isomorphic to wal-groups of automorphisms of tournament and show some of its properties.     

Tournaments and Vandermond's determinant

We prove that det |x_i^i–1|_{n × n} = Π_1≤i<i≤n (X_j – X_i) by associating a tournament to each term in the expansion of the product. All terms cancel except those corresponding to transitive tournaments, and their sum of the determinant.     

强连通竞赛图的圈分解

设T为n阶强连通竞赛图．本文通过详细刻画不能进行圈分解的强连通竞赛图的特征，证明了满足max{^ ，δ^-}≥5k-5和k≥2的强连通竞赛图T,能够分解为k个圈．     

t-可约竞赛图的得分向量

The definitions of t reducible and exactly t-reducible n tourna ments are introduced. Criteria are found for determining (i) whether a tourna ment with a given score vector R is t-reducible and (ii) whether it is exactly t-reducible.