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

Дискретн. анализ и исслед. опер., 2022, том 29, выпуск 1, страницы 46–55 (Mi da1292)

Эта публикация цитируется в 1 статье

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

А. В. Пяткинab, О. И. Черныхb

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

Аннотация: Открытым треугольником (ОТ) называется трёхвершинный подграф с двумя рёбрами, т. е. индуцированный путь длины $2$. В работе получена формула для максимально возможного числа ОТ в $n$-вершинных графах c $n$ рёбрами и дана полная характеризация графов, на которых достигается этот максимум. Ил. 2, библиогр. 10.

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

УДК: 519.17

Статья поступила: 26.07.2021
Переработанный вариант: 27.09.2021
Принята к публикации: 28.09.2021

DOI: 10.33048/daio.2022.29.723



© МИАН, 2025