Экстремальные эйлеровы ориентации циркулянтных графов Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2025, Volume: 22, Number: 2, Pages: 1717-1730 Pages count : 14 DOI: 10.33048/semi.2025.22.104 | ||||
| Tags | Eulerian orientation of graph, circuit, tournament | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
Abstract:
In this paper, we consider the achievability of the maximum and minimum numbers of occurrences of 3-circuits in Eulerian orientations of complete graphs missing a transitive subset of edges: complete graphs with an even number of vertices and a perfect matching removed, and those with an odd number of vertices and a Hamiltonian cycle removed. For each of these families of digraphs, we obtain upper and lower estimates for the number of 3-circuits and prove their achievability. Previously, orientations that are extreme with respect to the number of 4-circuit occurrences have been investigated in [1].
Cite:
Августинович С.В.
, Быков И.С.
, Пережогин А.Л.
, Кривоногова А.С.
Экстремальные эйлеровы ориентации циркулянтных графов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1717-1730. DOI: 10.33048/semi.2025.22.104 Scopus
Экстремальные эйлеровы ориентации циркулянтных графов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1717-1730. DOI: 10.33048/semi.2025.22.104 Scopus
Dates:
| Submitted: | Aug 25, 2025 |
| Published online: | Dec 31, 2025 |
Identifiers:
| Scopus: | 2-s2.0-105027515762 |
Citing:
Пока нет цитирований