ПОЧТИ ВСЕ n-ВЕРШИННЫЕ ГРАФЫ ЗАДАННОГО ДИАМЕТРА ГАМИЛЬТОНОВЫ?

Аннотация

Изучаются типичные гамильтоновы свойства класса n-вершинных графов фиксированного диаметра k. Построен новый класс типичных n-вершинных графов заданного диаметра. Получен ответ на вопрос С.В. Августиновича о гамильтоновости почти всех таких n-вершинных графов. Доказано, что почти все n-вершинные графы диаметра k=1,2,3 гамильтоновы, при этом почти все n-вершинные графы фиксированного диаметра k>=4 не являются гамильтоновыми графами. Все найденные типичные гамильтоновы свойства n-вершинных графов фиксированного диаметра k>=1 остаются также типичными для связных графов диаметра не менее k, а также для графов (не обязательно связных), содержащих кратчайшую цепь длины не менее k.