Laboratory of Mathematical Logic

Вторник, 10 октября, комната 106. Начало в 12:00.

Докладчик: А. В. Пастор.

ОБ УДАЛЕНИИ РЕБЕР ИЗ

-СВЯЗНОГО ГРАФА БЕЗ ПОТЕРИ

-СВЯЗНОСТИ

В 1969 году R. Halin доказал, что в любом

-связном графе, степени всех вершин которого не меньше

, есть ребро, удаление которого не нарушает

-связность графа. Эта теорема положила начало исследованию свойств минимальных

-связных графов, т.е.

-связных графов, которые теряют

-связность при удалении любого ребра, и поиску ребер, удаление которых не ведет к потере

-связности, в графах, не являющихся минимальными. В докладе будет произведен обзор известных результатов по данной теме, и будут представлены новые результаты, полученные докладчиком.