Relation between the simplicity of a tournament and various values of its diameter

Abstract

One of the most important types of graphs are tournaments, as they find practical application in many areas of our lives. Recall that a tournament is a complete oriented graph, that is, a directed graph, between each pair of its vertices there is a single arc, and there is a loop at each vertex. Like many algebraic objects, tournaments are made up of smaller elements. All the variety of their types allows us to describe such a structure as a congruence. The study of congruencies is of great interest, since knowledge of the scheme for constructing specific types of tournaments that have certain properties, such as, for example, the size of the diameter and simplicity, greatly simplifies the use of tournaments in practice, since it will be possible to build the necessary graph from scratch, and not check all known until the right one is found. Of great interest are simple tournaments, that is, tournaments whose congruence lattice consists of two elements. Taking into account the multiply increasing number of tournaments with the growth of dimension, the existence of a construction scheme will give a significant acceleration when choosing a tournament with given properties.

This paper describes tournaments that have an infinite diameter, as well as diameters n – 1 and n – 2. The structure of such tournaments is considered, and the question of their simplicity is investigated. It is proved that all n-vertex tournaments with diameter n – 1 are simple, but all tournaments with infinite diameter are not simple. Among tournaments with diameter n – 2, there are both simple and not simple tournaments.