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

Standard

Экстремальные эйлеровы ориентации циркулянтных графов. / Avgustinovich, Sergei Vladimirovich ; Bykov, Igor Sergeevich ; Perezhogin, Aleksei L.vovich и др.

в: Siberian Electronic Mathematical Reports, Том 22, № 2, 31.12.2025, стр. 1717-1730.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

BibTeX

@article{fb68857db00b4660a03bcb0518df8f35,

title = "Экстремальные эйлеровы ориентации циркулянтных графов",

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

keywords = "Eulerian orientation of graph, circuit, tournament",

author = "Avgustinovich, {Sergei Vladimirovich} and Bykov, {Igor Sergeevich} and Perezhogin, {Aleksei L.vovich} and Krivonogova, {Alena Sergeevna}",

note = "Августинович С.В., Быков И.С., Пережогин А.Л., Кривоногова А.С. Экстремальные эйлеровы ориентации циркулянтных графов // Сибирские электронные математические известия. - 2025. - Т. 22. - № 2. - 1473-1487. Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0017).",

year = "2025",

month = dec,

day = "31",

doi = "10.33048/semi.2025.22.104",

language = "русский",

volume = "22",

pages = "1717--1730",

journal = "Сибирские электронные математические известия",

issn = "1813-3304",

publisher = "Sobolev Institute of Mathematics",

number = "2",

}

RIS

TY - JOUR

T1 - Экстремальные эйлеровы ориентации циркулянтных графов

AU - Avgustinovich, Sergei Vladimirovich

AU - Bykov, Igor Sergeevich

AU - Perezhogin, Aleksei L.vovich

AU - Krivonogova, Alena Sergeevna

N1 - Августинович С.В., Быков И.С., Пережогин А.Л., Кривоногова А.С. Экстремальные эйлеровы ориентации циркулянтных графов // Сибирские электронные математические известия. - 2025. - Т. 22. - № 2. - 1473-1487. Исследование выполнено в рамках государственного задания ИМ СО РАН (проект № FWNF-2022-0017).

PY - 2025/12/31

Y1 - 2025/12/31

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

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

KW - Eulerian orientation of graph

KW - circuit

KW - tournament

UR - https://www.scopus.com/pages/publications/105027515762

UR - https://www.mendeley.com/catalogue/eac9c89d-3137-33cc-b3d2-6092ca85c7cd/

U2 - 10.33048/semi.2025.22.104

DO - 10.33048/semi.2025.22.104

M3 - статья

VL - 22

SP - 1717

EP - 1730

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

IS - 2

ER -

ID: 75460129