Простые и непростые регулярные турниры

Простые и непростые регулярные турниры

Шабаркова А. О., Абросимов М. Б.
Дискретный анализ и исследование операций, 33, 1, 114-123 (2026)
Скачать статью

УДК 519.172.3 
DOI: 10.33048/daio.2026.33.844

Аннотация:

Рассматриваются регулярные турниры относительно свойства простоты. Описаны виды турниров и их структура, и показано, какие из них простые, а какие нет. Доказывается, что для каждого нечётного $n$ существует по крайней мере один простой регулярный $n$-вершинный турнир. Для каждого $n = 3k$ существует турнир, не являющийся простым. Также приводится оценка числа турниров с такими структурами для различных значений размерности. 

Табл. 1, ил. 3, библиогр. 10.

Литература:
  1. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Физматлит, 1997. 368 с.
     
  2. Киреева А. В. Конгруэнции турниров // Студенты — ускорению научного прогресса: Сб. студ. науч. работ. Вып. 2. Саратов: Изд-во Саратов. ун-та, 1990. С. 3–5.
     
  3. Moon J. W. Topics on tournaments. New York: Holt, Rinehart, Winston, 1968. 138 p.
     
  4. Erdös P., Fried E., Hajnal A., Milner E. C. Some remarks on simple tournaments // Algebra Univers. 1972. V. 2, No. 2. P. 238–245.
     
  5. Habib M., Maurer M. C. On the $X$-join decomposition for undirected graphs // Discrete Appl. Math. 1979. V. 1. P. 201–207.
     
  6. Alrowily I. A. Some structural results on prime graphs // J. Adv. Math. 2019. V. 17. P. 362–369.
     
  7. Шабаркова А. О., Абросимов М. Б. Связь простоты турнира с различными значениями его диаметра // Int. J. Open Inf. Technol. 2022. Т. 10, № 6. С. 28–32.
     
  8. Haglin D. J. Number of unlabeled regular tournaments with $2n + 1$ nodes // The on-line encyclopedia of integer sequences. Highland Park, NJ: OEIS Found., 2025. URL: oeis.org/A096368 (accessed: 19.10.2025).
     
  9. Brinkmann G. Generating regular directed graphs // Discrete Math. 2012. V. 313. P. 1–7.
     
  10. McKay B. The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs // Combinatorica. 1990. V. 10. P. 367–377.
Шабаркова Александра Олеговна
  1. Саратовский национальный исследовательский гос. университет им. Н. Г. Чернышевского, 
    ул. Астраханская, 83, 410012 Саратов, Россия

E-mail: shabarkova_alex.andra@mail.ru 

Абросимов Михаил Борисович
  1. Саратовский национальный исследовательский гос. университет им. Н. Г. Чернышевского, 
    ул. Астраханская, 83, 410012 Саратов, Россия

E-mail: mic@rambler.ru 

Статья поступила 10 ноября 2025 г.
После доработки — 1 декабря 2025 г.
Принята к публикации 22 декабря 2025 г.

Abstract:

We consider regular tournaments with respect to the property of simplicity. The types of tournaments and their structure are described, while it is shown which of them are simple and which are not. We prove that for every odd $n$ there exists at least one simple regular $n$-vertex tournament and for every $n = 3k$ there is a tournament that is not simple. An estimate for the number of tournaments with such structures for different dimension values is also given. 

Tab. 1, illustr. 3, bibliogr. 10.

References:
  1. A. M. Bogomolov and V. N. Saliy, Algebraic Foundations of the Theory of Discrete Systems (Fizmatlit, Moscow, 1997) [Russian].
     
  2. A. V. Kireeva, Congruences of tournaments, in Students— To Acceleration of Scientific Progress, Vol. 2 (Izd. Saratov. Univ., Saratov, 1990), pp. 3–5 [Russian].
     
  3. J. W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).
     
  4. P. Erdös, E. Fried, A. Hajnal, and E. C. Milner, Some remarks on simple tournaments, Algebra Univers. 2 (2), 238–245 (1972).
     
  5. M. Habib and M. C. Maurer, On the $X$-join decomposition for undirected graphs, Discrete Appl. Math. 1, 201–207 (1979).
     
  6. I. A. Alrowily, Some structural results on prime graphs, J. Adv. Math. 17, 362–369 (2019).
     
  7. A. O. Shabarkova and M. B. Abrosimov, Relation between the simplicity of a tournament and various values of its diameter, Int. J. Open Inf. Technol. 10 (6), 28–32 (2022) [Russian].
     
  8. D. J. Haglin, Number of unlabeled regular tournaments with $2n + 1$ nodes, in The On-Line Encyclopedia of Integer Sequences (OEIS Found., Highland Park, NJ, 2025), URL: oeis.org/A096368 (accessed: 19.10.2025).
     
  9. G. Brinkmann, Generating regular directed graphs, Discrete Math. 313, 1–7 (2012).
     
  10. B. McKay, The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs, Combinatorica 10, 367–377 (1990).