A representation theorem and Z-cyclic whist tournaments

Let E denote the group of units (i.e., the reduce set of residues) in the ring Z. Here we consider q,p to be primes, q ≡ 3 (mod 4), q ? 7, p ≡ 1 (mod 4). Let W denote a common primitive root of 3, q, and p². If H denotes the (normal) subgroup of E that is generated by {?1, W}, we show that the factor group E/H is cyclic by demonstrating the existence of an element x in E such that the coset xH has order equal to |E/H|. This order is given by gcd(p^n?1(p ? 1),q ? 1). This representation of E/H is exploited via an appropriate construction to produce Z-cyclic whist tournaments for 3qpⁿ players. Consequently these results extend those of an early study of Wh(3qpⁿ) that was restricted to gcd(p^n?1(p ? 1),q ? 1) = 2. © 1995 John Wiley & Sons, Inc.     

Cyclically resolvable designs and triple whist tournaments

We construct cyclically resolvable (v, 4, 1) designs and cyclic triple whist tournaments TWh(v) for all v of the form 3p…p + 1, where the p_i are primes ≡ 1 (mod 4), such that each P₁ ? 1 is divisible by the same power of 2. © 1993 John Wiley & Sons, Inc.     

Z-cyclic triplewhist tournaments when the number of players involves primes of the form 8u + 5

When the number of players, v, in a whist tournament, Wh(v), is ≡ 1 (mod 4) the only instances of a Z-cyclic triplewhist tournament, TWh(v), that appear in the literature are for v = 21,29,37. In this study we present Z-cyclic TWh(v) for all v ∈ T = {v = 8u + 5: v is prime, 3 ≤ u ≤ 249}. Additionally, we establish (1) for all v ∈ T there exists a Z-cyclic TWh(vⁿ) for all n ≥ 1, and (2) if v_i ∈ T, i = 1,…,n, there exists a Z-cyclic TWh(v… v) for all ?_i ≥ 1. It is believed that these are the first instances of infinite classes of Z-cyclic TWh(v), v ≡ 1 (mod 4). © 1994 John Wiley & Sons, Inc.     

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     

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.     

Spectral characterizations of tournaments

Characterizing graphs by the spectra of various matrices associated with the graphs has long been an important topic in spectral graph theory. However, it is generally very hard to show a given graph to be determined by its spectrum. This paper gives a simple criterion for a tournament to be determined by its adjacency spectrum. More precisely, let G be a tournament of order n with adjacency matrix A, and $W_A(G)=[e,Ae,...,A^{n?1}e]$ be its walk matrix, where e is the all-one vector. We show that, for any self-converse tournament G, if $\det ?W_A(G)$ is square-free, then G is uniquely determined by its adjacency spectrum among all tournaments. The result is somewhat unexpected, which was achieved by employing some recent tools developed by the second author for showing a graph to be determined by its generalized spectrum. The key observation is that for a tournament G, the complement of G coincides with the converse of G, and hence a certain equivalence between the ordinary adjacency spectrum and the generalized (skew)-adjacency spectrum for G can be established. Moreover, some equivalent formulations of the above result, as well as some related ones are also presented.     

Excluding pairs of tournaments

The Erdős–Hajnal conjecture states that for every given undirected graph H there exists a constant such that every graph G that does not contain H as an induced subgraph contains a clique or a stable set of size at least . The conjecture is still open. Its equivalent directed version states that for every given tournament H there exists a constant such that every H‐free tournament T contains a transitive subtournament of order at least . In this article, we prove that for several pairs of tournaments, H₁ and H₂, there exists a constant such that every ‐free tournament T contains a transitive subtournament of size at least . In particular, we prove that for several tournaments H, there exists a constant such that every ‐free tournament T, where stands for the complement of H, has a transitive subtournament of size at least . To the best of our knowledge these are first nontrivial results of this type.     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

Alternation acyclic tournaments

We define a tournament to be alternation acyclic if it does not contain a cycle in which descents and ascents alternate. Using a result by Athanasiadis on hyperplane arrangements, we show that these tournaments are counted by the median Genocchi numbers. By establishing a bijection with objects defined by Dumont, we show that alternation acyclic tournaments in which at least one ascent begins at each vertex, except for the largest one, are counted by the Genocchi numbers of the first kind. Unexpected consequences of our results include a pair of ordinary generating function formulas for the Genocchi numbers of both kinds and a simple model for the normalized median Genocchi numbers.     

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.     

Z-cyclic triplewhist tournaments—The noncompatible case,part I

Two odd primes odd, are said to be noncompatible if b₁ ≠ b₂. For all noncompatible (ordered) pairs of primes (p₁, p₂) such that p_i ≡ p_i < 200, i = 1,2 we establish the existence of Z-cyclic triplewhist tournaments on 3p₁ p₂ + 1 players. It is believed that these results are the first examples of such tournaments, indeed the first examples of Z-cyclic whist tournaments for such players. In Part 2 we extend the results of this study and establish the existence of Z-cyclic triplewhist tournaments on players for all α₁ ≥ 1, α₂ ≥ 1 and p₁, p₂ as described above. © 1997 John Wiley & Sons, Inc.     

Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.     

Decomposability index of tournaments

Given a tournament $T$, a module of $T$ is a subset $X$ of $V\left(T\right)$ such that for $x,y\in X$ and $v\in V\left(T\right)?X$, $(x,v)\in A\left(T\right)$ if and only if $(y,v)\in A\left(T\right)$. The trivial modules of $T$ are $?$, $\left\{u\right\}$ $(u\in V\left(T\right))$ and $V\left(T\right)$. The tournament $T$ is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of $T$, denoted by $\delta \left(T\right)$, is the smallest number of arcs of $T$ that must be reversed to make $T$ indecomposable. For $n\ge 5$, let $\delta \left(n\right)$ be the maximum of $\delta \left(T\right)$ over the tournaments $T$ with $n$ vertices. We prove that $?\frac{n+1}{4}?\le \delta \left(n\right)\le ?\frac{n?1}{3}?$ and that the lower bound is reached by the transitive tournaments.     

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.     

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