|
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.
Citation:
A. O. Shabarkova, M. B. Abrosimov, “On the structure of tournaments consisting of only kings”, Prikl. Diskr. Mat. Suppl., 2024, no. 17, 154–156
Linking options:
https://www.mathnet.ru/eng/pdma670 https://www.mathnet.ru/eng/pdma/y2024/i17/p154
|
|