On the structure of local tournaments (Q1892843): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:07, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of local tournaments |
scientific article |
Statements
On the structure of local tournaments (English)
0 references
2 July 1995
0 references
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 arc 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 graph.
0 references
local tournament
0 references
circular arc graphs
0 references
structure theorems
0 references
interval graphs
0 references