Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 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$.