RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2024, том 21, выпуск 1, страницы 370–382 (Mi semr1691)

Дискретная математика и математическая кибернетика

Контуры малой длины в эйлеровых ориентациях графов

А. Л. Пережогинa, И. С. Быковb, С. В. Августиновичa

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

Аннотация: In this paper we investigate estimates for number of 3-, 4- and 5-circuits in eulerian tournaments and 4-circuits in eulerian orientations of complete bipartite graphs and hypercubes. By using obtained relations, we prove uniqueness (up to isomorphism) of orientations, which reach maximum number of 4-circuits in all graph families mentioned above.

Ключевые слова: Eulerian orientation of graph, circuit, tournament, complete bipartite graph, boolean cube.

УДК: 519.175

MSC: 05C20

Поступила 12 декабря 2023 г., опубликована 6 июня 2024 г.

DOI: doi.org/10.33048/semi.2024.21.028



© МИАН, 2025