|
О максимальном числе открытых треугольников в графах с одинаковым числом вершин и рёбер
А. В. Пяткинab, О. И. Черныхb a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия
Аннотация:
Открытым треугольником (ОТ) называется трёхвершинный подграф с двумя рёбрами, т. е. индуцированный путь длины $2$. В работе получена формула для максимально возможного числа ОТ в $n$-вершинных графах c $n$ рёбрами и дана полная характеризация графов, на которых достигается этот максимум. Ил. 2, библиогр. 10.
Ключевые слова:
открытые треугольники, индуцированные подграфы, унициклические графы.
Статья поступила: 26.07.2021 Переработанный вариант: 27.09.2021 Принята к публикации: 28.09.2021
Образец цитирования:
А. В. Пяткин, О. И. Черных, “О максимальном числе открытых треугольников в графах с одинаковым числом вершин и рёбер”, Дискретн. анализ и исслед. опер., 29:1 (2022), 46–55
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1292 https://www.mathnet.ru/rus/da/v29/i1/p46
|
|