Home

Пятница 15 ноября, 15-15, ауд. 203

Пятница, 15 ноября, ауд. 203. Начало в 15:15.

Докладчик: Д.В. Карпов (ПОМИ РАН).

Тема: Минимальные двусвязные графы.

Abstract

Двусвязный граф называется минимальным, если при удалении любого его ребра теряется двусвязность. В работе доказано, что для любого минимального двусвязного графа $ G $ существует последовательность минимальных двусвязных графов $ H_1 $, ..., $ H_n=G $, в которой граф $ H_1 $ имеет только вершины степеней 2 и 3, а каждый следующий граф получается из предыдущего стягиванием ребра, соединяющего две вершины степени не менее 3.

В работе изучаются минимальные двусвязные графы, содержащие наименьшее возможное число вершин степени~2. Обозначим множество таких графов на $ n $ вершинах через $ \GM(n) $. Как известно, в графах из $ \GM(n) $ должно быть ровно по $ \lceil{n+4\over 3}\rceil $ вершин степени~2. Доказывается, что для $ \GM(3k+2) $ при $ k\ge 1 $ состоит из графов вида $ G_T $, где $ T $ --- дерево на $ k $ вершинах, степени вершин которого не превосходят 3. Граф $ G_T $ строится из двух копий дерева $ T $: к каждой паре соответствующих вершин которых добавляются смежные с ними вершины степени 2 (так, чтобы степени всех вершин исходных двух деревьев стали равнны 3). Графы из $ \GM(3k) $ и $ \GM(3k+1) $ также характеризованы с помощью графов вида $ G_T $.