RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2025, том 32, выпуск 2, страницы 107–121 (Mi da1381)

Об экстремальных по числу открытых треугольников графах с малым числом рёбер

А. В. Пяткин

Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Аннотация: Открытым треугольником (ОТ) в неориентированном графе называется индуцированный подграф из трёх вершин ровно с двумя рёбрами. Рассматривается класс графов, в котором числа вершин и рёбер отличаются на фиксированную константу $c.$ Получена полная характеризация экстремальных по числу ОТ графов в таком классе с не менее чем $c+7$ вершинами. Ил. 1, библиогр. 12.

Ключевые слова: открытый треугольник, индуцированный подграф, разреженный граф.

УДК: 519.17

Статья поступила: 19.03.2025
Переработанный вариант: 26.03.2025
Принята к публикации: 22.04.2025

DOI: 10.33048/daio.2025.32.830



© МИАН, 2025