Toppling kings in multipartite tournaments by introducing new kings

Let and be two n-tuples of nonnegative integers. An all-4-kings n-partite tournament T(V₁,V₂,…V_n) is said to have a -property if there exists an n-partite tournament T₁(W₁,W₂,…,W_n) such that for each i∈{1,…,n}:

(1)

V_i⊆W_i;

(2)

exactly t_i 4-kings of V_i are not 4-kings in T₁;

(3)

exactly c_i 4-kings of W_i are not vertices of V_i.

We describe all pairs such that there exists an n-partite tournament having -property.     

Out-arc pancyclicity of vertices in tournaments

Yao, Guo and Zhang [T. Yao, Y. Guo, K. Zhang, Pancyclic out-arcs of a vertex in a tournament, Discrete Appl. Math. 99 (2000) 245-249.] proved that every strong tournament contains a vertex u such that every out-arc of u is pancyclic. In this paper, we prove that every strong tournament with minimum out-degree at least two contains two such vertices. Yeo [A. Yeo, The number of pancyclic arcs in a k-strong tournament, J. Graph Theory 50 (2005) 212-219.] conjectured that every 2-strong tournament has three distinct vertices {x,y,z}, such that every arc out of x,y and z is pancyclic. In this paper, we also prove that Yeo’s conjecture is true.     

Antidirected Hamiltonian paths and directed cycles in tournaments

We prove that in a tournament of odd order $n\ge 5$, the number of antidirected Hamiltonian paths starting with a forward arc and the number of Hamiltonian circuits have the same parity.     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

On the 3-kings and 4-kings in multipartite tournaments

Koh and Tan gave a sufficient condition for a 3-partite tournament to have at least one 3-king in [K.M. Koh, B.P. Tan, Kings in multipartite tournaments, Discrete Math. 147 (1995) 171-183, Theorem 2]. In Theorem 1 of this paper, we extend this result to n-partite tournaments, where n?3. In [K.M. Koh, B.P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Math. 154 (1996) 281-287, K.M. Koh, B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167/168 (1997) 411-418] Koh and Tan showed that in any n-partite tournament with no transmitters and 3-kings, where n?2, the number of 4-kings is at least eight, and completely characterized all n-partite tournaments having exactly eight 4-kings and no 3-kings. Using Theorem 1, we strengthen substantially the above result for n?3. Motivated by the strengthened result, we further show that in any n-partite tournament T with no transmitters and 3-kings, where n?3, if there are r partite sets of T which contain 4-kings, where 3?r?n, then the number of 4-kings in T is at least r+8. An example is given to justify that the lower bound is sharp.     

On nice and injective-nice tournaments

One way of defining an oriented colouring of a directed graph $\overrightarrow{G}$ is as a homomorphism from $\overrightarrow{G}$ to a target directed graph $\overrightarrow{H}$, and an injective oriented colouring of $\overrightarrow{G}$ can be defined as a homomorphism from $\overrightarrow{G}$ to a target directed graph $\overrightarrow{H}$ such that no two in-neighbours of a vertex of $\overrightarrow{G}$ have the same image. Oriented colourings may be constructed using target directed graphs that are nice, as defined by Hell et al. (2001). We extend the work of Hell et al. by considering target graphs that are tournaments, characterizing nice tournaments, and proving that every nice tournament on $n$ vertices is $k$-nice for some $k\le n+2$. We also give a characterization of tournaments that are nice but not injective-nice.     

On the existence of strong Nash equilibria

This paper investigates the existence of strong Nash equilibria (SNE) in continuous and concave games. It is shown that the coalition consistency property introduced in the paper, together with concavity and continuity of payoffs, permits the existence of SNE in games with compact and convex strategy spaces. We also characterize the existence of SNE by providing necessary and sufficient conditions. We suggest an algorithm for computing SNE. The results are illustrated with applications to economies with multilateral environmental externalities and to the static oligopoly model.     

Resistance and conductance in structured Zermelo tournaments

The mathematical model that Zermelo developed for ranking by paired comparisons and that was later popularized by Bradley and Terry has several attractive theoretical properties, but computation of the associated ratings may involve solution of a system of several high-degree polynomial equations in several variables. This paper describes how to define quantities analogous to electrical resistance and conductance for certain generalized tournaments in such a way that these quantities are well-behaved with respect to certain types of decomposition of tournaments and permit comparison of the ratings of pairs of nodes. Application of this theory is illustrated through consideration of specific examples.     

On the maximum skew spectral radius and minimum skew energy of tournaments

The maximum skew spectral radius and the minimum skew energy among tournaments of a fixed order are shown to be achieved uniquely, up to switching and labeling, by the transitive tournament.     

On the uniqueness of strong solution to the incompressible Navier-Stokes equations with damping

In this paper, we show that the Cauchy problem of the incompressible Navier-Stokes equations with damping α|u|^β−1u(α>0) has global strong solution for any β>3 and the strong solution is unique when 3<β?5. This improves earlier results.     

A general central limit theorem for strong mixing sequences

A central limit theorem for strong mixing sequences is given that applies to both non-stationary sequences and triangular array settings. The result improves on an earlier central limit theorem for this type of dependence given by Politis, Romano and Wolf in 1997.     

Local existence and uniqueness of strong solutions to 3-D stochastic Navier-Stokes equations

For stochastic Navier-Stokes equations in a 3-dimensional bounded domain we first show that if the initial value is sufficiently regular, then martingale solutions are strong on a random time interval and we estimate its length. Then we prove the uniqueness of the strong solution in the class of all martingale solutions. Received November 15, 1995     

New existence and nonexistence results for strong external difference families

In this paper, we use character-theoretic techniques to give new nonexistence results for $(n,m,k,\lambda )$-strong external difference families (SEDFs). We also use cyclotomic classes to give two new classes of SEDFs with $m=2$.