✦ LIBER ✦

On the Structure of Local Tournaments

✍ Scribed by J. Huang

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 1001 KB
Volume: 63
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1016

No coin nor oath required. For personal study only.

✦ Synopsis

A local tournament is an oriented graph in which the inset, as well as the outset, of every vertex induces a tournament. Local tournaments are interesting in their own right, as they share many nice properties of tournaments. They are also of interest because of their relation to proper circular arc graphs. Indeed, a connected graph can be oriented as a local tournament if and only if it is a proper circular arc graph. Thus understanding the structure of local tournaments also sheds light on the structure of proper circular arc graphs. We describe a method to generate all local tournaments by performing some simple operations on some simple basic oriented graphs. As a consequence we obtain a description of all local tournaments with the same underlying proper circular are graph. Similar structural information is obtained for non-strong local tournaments, which are related to proper interval graphs. These structure theorems have already been used to design optimal algorithms to recognize proper circular arc graphs, proper interval graphs, and local tournaments (and to represent them if possible) and to find a maximum clique in a represented proper circular arc graphs. I 1995 Academic Press, Inc.

📜 SIMILAR VOLUMES

On homomorphisms to acyclic local tourna

On homomorphisms to acyclic local tournaments

✍ Pavol Hell; Huishan Zhou; Xuding Zhu 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 233 KB

## Abstract A homomorphism of a digraph to another digraph is an edgepreserving vertex mapping. A local tournament is a digraph in which the inset as well as the outset of each vertex induces a tournament. Thus acyclic local tournaments generalize both directed paths and transitive tournaments. In

Locally semicomplete digraphs: A general

Locally semicomplete digraphs: A generalization of tournaments

✍ Jørgen Bang-Jensen 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 1022 KB

## Abstract In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex __x__ the vertices dominated by __x__ induce a semicomplete digraph and the vertices that dominate __x__

On the evolution of a random tournament

✍ Tomasz Łuczak; Andrzej Ruciński; Jacek Gruszka 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 280 KB

On the existence of triplewhist tourname

On the existence of triplewhist tournaments TWh(v)

✍ Y. Lu; L. Zhu 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB 👁 2 views

It is well known that a triplewhist tournament TWh(v) exists only if v ≡ 0 or 1 (mod 4) and v = 5, 9. In this article, we introduce a new concept TWh-frame and use it to show that the necessary condition for the existence of a TWh(v) is also sufficient with a handful possible exceptions of v ∈ {12,

On the number of Hamiltonian cycles in t

On the number of Hamiltonian cycles in tournaments

✍ Carsten Thomassen 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 949 KB

The main results assert that the minimum number of Hamiltonian bypasses in a strong tournament of order n and the minimum number of Hamiltonian cycles in a 2-connected tournament of order n increase exponentially with n. Furthermore, the number of Hamiltonian cycles in a tournament increases at leas

On the Structure of the Irreducible Poly

On the Structure of the Irreducible Polynomials Over Local Fields

✍ N. Popescu; A. Zaharescu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 695 KB

The paper is concerned with the structure of irreducible polynomials in one variable over a local field \((K, v)\). The main achievement is the definition of a system \(P(f)\) of invariant factors for each monic irreducible polynomial \(f \in K[X]\). It is proved that these invariants are characteri