Home

Семинар 10 октября 2000 года

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

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

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