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

Дискретн. анализ и исслед. опер., 2024, том 31, выпуск 3, страницы 144–152 (Mi da1357)

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

А. В. Пяткин

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

Аннотация: Подмножество из трёх вершин, порождающее подграф ровно с двумя рёбрами, будем называть открытым треугольником (ОТ). Рассматривается задача поиска графов с максимальным числом ОТ. Доказано, что в классе графов, когда число рёбер превышает число вершин на фиксированную константу, такой граф единствен при достаточно большом числе вершин. Библиогр. 11.

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

УДК: 519.17

Статья поступила: 25.01.2024
Переработанный вариант: 20.02.2024
Принята к публикации: 22.03.2024

DOI: 10.33048/daio.2024.31.793


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2024, 18:3, 516–520


© МИАН, 2025