"Записки научных семинаров ПОМИ"
Том 417, стр. 106-127
Минимальные двусвязные графы
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН
Фонтанка 27, 191023 Санкт-Петербург, Россия;
СПбГУ Университетский пр., 28, 198504,
Санкт-Петербург, Старый Петергоф
dvk0@yandex.ru
- Аннотация:
Двусвязный граф называется минимальным, если при удалении любого
его ребра теряется двусвязность. В работе изучаются минимальные двусвязные графы, содержащие
наименьшее возможное число вершин степени 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$.
Библ. -- 12 назв.
- Ключевые слова:связность, двусвязный граф, минимальный двусвязный граф
[connectivity, biconnected graph, decomposition, blocks]
Полный текст(.pdf)