On the structure of local tournaments
type: Item
instance of: scholarly article
title: On the structure of local tournaments
zbMATH Open document ID: 0820.05029
author: Jing Huang
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 767691
zbMATH Keywords: local tournament
zbMATH Keywords: circular arc graphs
zbMATH Keywords: structure theorems
zbMATH Keywords: interval graphs
reviewed by: Nan-Jing Huang
MaRDI profile type: Publication
full work available at URL: jctb.1995.1016
OpenAlex ID: W2037424045
DOI: 10.1006/JCTB.1995.1016
description: scientific article; zbMATH DE number 767691