Applied Theory of Coding, Automata and Graphs

On the structure of tournaments consisting of only kings

A. O. Shabarkova, M. B. Abrosimov

Saratov State University

Abstract: The structure of some classes of tournaments consisting of only kings and their number are considered, and it is also shown that such tournaments are not simple. A tournament is called regular if all its vertices have the same entry and exit degrees. The vertex $v$ of the tournament is king if the length of the path from $v$ to any other vertex is no more than 2. The following main result has been obtained: tournament $T$ of dimension $n$, where $n$ is odd, consisting of only kings, $k$ rows of the distance matrix of which have the form $(1^{(n-1)/2},2^{(n -1)/2})$, and the rest $(1^{(n-i-1)},2^i )$, where $i\in\{1,\ldots,(n-k)/2,(n+k)/2-1,\ldots,n-2\}$, has the following structure: at the base there is a regular tournament of dimension $k$, to which two vertices $v_1$ and $v_2$ are sequentially added as follows: arcs lead from vertex $v_1$ to all vertices of tournament $T^*$; from each vertex of $T^*$ there are arcs leading to vertex $v_2$; and there is also an arc from $v_2$ to $v_1$, where $T^*$ is the tournament obtained at the previous step, until the dimension of the resulting tournament is equal to $n$. Such a tournament is not simple, and for each $n$ there are as many such tournaments as there are regular tournaments with the number of vertices equal to that of the tournament at the base.

Keywords: graph theory, tournament, distance matrix.

UDC: 519.17

DOI: 10.17223/2226308X/17/40