On the structure of local tournaments (Q1892843): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
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
    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

    Identifiers