A bound on the generalized competition index of a primitive matrix using Boolean rank

For a positive integer m where 1?m?n, the m-competition index (generalized competition index) of a primitive digraph is the smallest positive integer k such that for every pair of vertices x and y, there exist m distinct vertices v₁,v₂,…,v_m such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. The m-competition index is a generalization of the scrambling index and the exponent of a primitive digraph. In this study, we determine an upper bound on the m-competition index of a primitive digraph using Boolean rank and give examples of primitive Boolean matrices that attain the bound.     

Generalized competition index of a primitive digraph

For positive integers k and m, and a digraph D, the k-step m-competition graph of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v₁,v₂,…,v_m in D such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph.     

Generalized competition index of primitive digraphs

For any positive integers k and m, the k-step m-competition graph C _m ^k (D) of a digraph D has the same set of vertices as D and there is an edge between vertices x and y if and only if there are distinct m vertices v₁, v₂, · · ·, v _m in D such that there are directed walks of length k from x to v _i and from y to v _i for all 1 ≤ i ≤ m. The m-competition index of a primitive digraph D is the smallest positive integer k such that C _m ^k (D) is a complete graph. In this paper, we obtained some sharp upper bounds for the m-competition indices of various classes of primitive digraphs.     

The domination and competition graphs of a tournament

Vertices x and y dominate a tournament T if for all vertices z ≠ x, y, either x beats z or y beats z. Let dom(T) be the graph on the vertices of T with edges between pairs of vertices that dominate T. We show that dom(T) is either an odd cycle with possible pendant vertices or a forest of caterpillars. While this is not a characterization, it does lead to considerable information about dom(T). Since dom(T) is the complement of the competition graph of the tournament formed by reversing the arcs of T, complementary results are obtained for the competition graph of a tournament. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 103–110, 1998     

On a generalized Cournot oligopolistic competition game

We consider a model whereby players compete for a set of shared resources to produce and sell substitute products in the same market, which can be viewed as a generalization of the classical Cournot oligopolistic competition model, or, from a different angle, the Wardrop type routing model. In particular, we suppose that there are K players, who compete for the usage of resources as well as the sales of the end-products. Moreover, the unit costs of the shared resources and the selling prices of the products are assumed to be affine linear functions in the consumption/production quantities. We show that the price of anarchy in this case is lower bounded by 1/K, and this bound is essentially tight, which manifests the harsh nature of the competitive market for the producers.     

On a conjecture about the generalized exponent of primitive matrices

In this paper the conjecture on the kth upper multiexponent of primitive matrices proposed by R.A. Brualdi and Liu are completely proved.     

A reversal index for tournament matrices

Given a tournament matrix T, its reversal indexi_R(T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R(T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R(T)≤[(n-1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n-1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

On the decisiveness of a game in a tournament

In sport tournaments in which teams are matched two at a time, it is useful for a variety of reasons to be able to quantify how important a particular game is. The need for such quantitative information has been addressed in the literature by several more or less simple measures of game importance. In this paper, we point out some of the drawbacks of those measures and we propose a different approach, which rather targets how decisive a game is with respect to the final victory. We give a definition of this idea of game decisiveness in terms of the uncertainty about the eventual winner prevailing in the tournament at the time of the game. As this uncertainty is strongly related to the notion of entropy of a probability distribution, our decisiveness measure is based on entropy-related concepts. We study the suggested decisiveness measure on two real tournaments, the 1988 NBA Championship Series and the UEFA 2012 European Football Championship (Euro 2012), and we show how well it agrees with what intuition suggests. Finally, we also use our decisiveness measure to objectively analyse the recent UEFA decision to expand the European Football Championship from 16 to 24 nations in the future, in terms of the overall attractiveness of the competition.     

On the existence of specified cycles in a tournament

For 2 ≦ p ≦n and n ≧ 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p- 1 consecutives edges. In this paper, we prove that every tournament of order n ≧ 7 contains D(n, p) for p = 2, 3, …, n. Furthermore, we determine the tournaments of order n, 3 ≦ n ≦ 6, which do not contain D(n, p) for some p.     

On the score sheets of a round-robin football tournament

The set of (ordered) score sheets of a round-robin football tournament played between n teams together with the pointwise addition has the structure of an affine monoid. In this paper we study (using both theoretical and computational methods) the most important invariants of this monoid, namely the Hilbert basis, the multiplicity, the Hilbert series and the Hilbert function.     

On claws belonging to every tournament

A directed graph is said to ben-unavoidable if it is contained as a subgraph by every tournament onn vertices. A number of theorems have been proven showing that certain graphs aren-unavoidable, the first being Rédei's results that every tournament has a Hamiltonian path. M. Saks and V. Sós gave more examples in [6] and also a conjecture that states: Every directed claw onn vertices such that the outdegree of the root is at most [n/2] isn-unavoidable. Here a claw is a rooted tree obtained by identifying the roots of a set of directed paths. We give a counterexample to this conjecture and prove the following result:any claw of rootdegreen/4 is n-unavoidable.     

Scrambling index set of primitive digraphs

The scrambling index k(D)$k(D)$ of a primitive digraph D is the smallest positive integer k such that for every pair of vertices x and y, there exists a vertex v such that there exist directed walks of length k from x to v and from y to v. In this paper, we study the scrambling index set of primitive digraphs.     

Existence results for generalized balanced tournament designs with block size 3

A generalized balanced tournament design,GBTD(n, k) defined on akn-setV, is an arrangement of the blocks of a (kn, k, k–1)-BIBD defined onV into ann× (kn–1), array such that (1) every element ofV is contained in precisely one cell of each column, and (2) every element ofV is contained in at mostk cells of each row. In this paper, we completely determine the spectrum ofGBTD(n, 3). In addition we prove the exitence of factoredGBTD(n, 3) forn a positive integer,n4, with at most one possible exception.This research was supported by a Postdoctoral membership at the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455.     

Near generalized balanced tournament designs with block sizes 4 and 5

A near generalized balanced tournament design, or an NGBTD(k,m) in short, is a (km + 1, k, k − 1)-BIBD defined on a (km +1)-set V. Its blocks can be arranged into an m × (km + 1) array in such a way that (1) the blocks in every column of the array form a partial parallel class partitioning V[x] for some point x, and (2) every element of V is contained in precise k cells of each row. In this paper, we completely solve the existence of NGBTD(4,m) and almost completely solve the existence of NGBTD(5,m) with four exceptions.