The definition for the domination graph of a tournament states that it has the same vertices as the tournament with an edge between two vertices if every other vertex is beaten by at least one of them. In this paper two new types of domination graphs are defined by using different relaxations of the adjacency definition. The first type is formed by reducing the number of vertices which must be dominated by a pair of vertices and the second by increasing the number of steps allowable for domination. Properties of these new types of domination graphs are presented with comparison between them where appropriate. In particular a full characterisation of each type is given for rotational tournements. |
Keywords
Math Review Classification
Last Updated
9 August 1999
Length
12 pages
Availability
This article is available in: