Экстремальные эйлеровы ориентации циркулянтных графов | Sciact - Система учета научной деятельности ИМ СО РАН

Экстремальные эйлеровы ориентации циркулянтных графов Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2025, Том: 22, Номер: 2, Страницы: 1717-1730 Страниц : 14 DOI: 10.33048/semi.2025.22.104

Ключевые слова

Eulerian orientation of graph, circuit, tournament

Авторы

Августинович С.В. ¹ , Быков И.С. ² , Пережогин А.Л. ¹ , Кривоногова А.С. ²

Организации

1	Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
2	Novosibirsk State University, Pirogova str., 1, 630090, Novosibirsk, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0017

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].

Августинович С.В. , Быков И.С. , Пережогин А.Л. , Кривоногова А.С.
Экстремальные эйлеровы ориентации циркулянтных графов
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2025. Т.22. №2. С.1717-1730. DOI: 10.33048/semi.2025.22.104 Scopus

Поступила в редакцию:	25 авг. 2025 г.
Опубликована online:	31 дек. 2025 г.

Scopus:

2-s2.0-105027515762

Пока нет цитирований