Domination Conditions for Tournaments

Patricia McKenna, Margaret Morton and Jamie Sneddon

Abstract

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: