Том 5, серия 1, номер 2, 1998 г., Стр. 3-27

УДК 519.17
Д. Л. Белоцерковский
Об одной задаче перечисления экстремальных графов

Аннотация:
Пусть $\mathfrak G(n,d_1,d_2)$ есть совокупность $n$-вершинных графов диаметра не более $d_1$ таких, что после удаления из графа любой вершины или любого ребра получается граф диаметра не более $d_2$. Любой граф из $\mathfrak G(n,d_1,d_2)$ с минимально возможным числом ребер называется экстремальным. Цель работы состоит в нахождении всех экстремальных графов из $\mathfrak G(n,3,4)$.
Ил. 17, библиогр. 13.

Белоцерковский Д. Л. ¹
1. Институт проблем передачи информации РАН,
Большой Каретный пер., 19, 101447 Москва, ГСП-4, Россия

Статья поступила 10 мая 1996 г.
Исправленный вариант — 16 марта 1998 г.