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