Laboratory of Mathematical Logic at PDMI

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

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

ОБ УДАЛЕНИИ РЕБЕР ИЗ $K$-СВЯЗНОГО ГРАФА БЕЗ ПОТЕРИ $K$-СВЯЗНОСТИ
В 1969 году R. Halin доказал, что в любом $k$-связном графе, степени всех вершин которого не меньше $k+1$, есть ребро, удаление которого не нарушает $k$-связность графа. Эта теорема положила начало исследованию свойств минимальных $k$-связных графов, т.е. $k$-связных графов, которые теряют $k$-связность при удалении любого ребра, и поиску ребер, удаление которых не ведет к потере $k$-связности, в графах, не являющихся минимальными. В докладе будет произведен обзор известных результатов по данной теме, и будут представлены новые результаты, полученные докладчиком.