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     

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     

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.     

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.     

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.     

强连通竞赛图的圈分解

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

传递的二部竞赛图的性质

Abipartitetournamentistransitiveifitcontainsnocycles.Becausetransitivem ×nbi partitetournamentisn’tuniqueintheisomorphicsense,theproblemsoftransitivebipartitetournamentsarecomplicated .Hence ,BEINEKELWandMOONJW gaveacriterionforde terminingwhetherascoreorderedpaircontainssometransitivebipartitetournament(see [1 ]) .Theenumerationoftransitivebipartitetournamentswasdiscussedby [2 ].LetTm ,n =(V ,U ,E) beam ×nbipartitetournamentwith｜V｜=mand｜U｜=n .Denotebyd(w)thescoreofvertexw .Th…     

Domination Number of Certain Infinite Tournaments

We consider tournaments defined by several linear orderings of the vertex set according to some rule specifying the direction of each arc depending only on the order of the end vertices in each of the orderings. In the finite case, it was proved in Alon et al. (J Comb Theory Ser B 96:374–387, 2006) that the domination number of such tournaments is bounded in terms of the rule only. We show that for infinite tournaments, under some natural restrictions, the domination number is always finite, though in general cannot be bounded. We give some sufficient conditions under which there exists an upper bound in terms of the rule and/or the order types, and provide examples demonstrating that the bounds obtained are not very far from truth.     

强竞赛图中包含一条路的圈

设T为强竞赛图,P为T中一条长度为2的路.给出了T存在包含P的一些圈的充分条件.     

On n-partite Tournaments with Unique n-cycle

An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc. 21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments.