|
О максимальном числе открытых треугольников в графах с малым числом рёбер
А. В. Пяткин Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Аннотация:
Подмножество из трёх вершин, порождающее подграф ровно с двумя рёбрами, будем называть открытым треугольником (ОТ). Рассматривается задача поиска графов с максимальным числом ОТ. Доказано, что в классе графов, когда число рёбер превышает число вершин на фиксированную константу, такой граф единствен при достаточно большом числе вершин. Библиогр. 11.
Ключевые слова:
открытый треугольник, индуцированный подграф, разреженный граф.
Статья поступила: 25.01.2024 Переработанный вариант: 20.02.2024 Принята к публикации: 22.03.2024
Образец цитирования:
А. В. Пяткин, “О максимальном числе открытых треугольников в графах с малым числом рёбер”, Дискретн. анализ и исслед. опер., 31:3 (2024), 144–152; J. Appl. Industr. Math., 18:3 (2024), 516–520
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da1357 https://www.mathnet.ru/rus/da/v31/i3/p144
|
Статистика просмотров: |
Страница аннотации: | 48 | PDF полного текста: | 4 | Список литературы: | 5 | Первая страница: | 5 |
|