"Записки научных семинаров ПОМИ"
Том 518, стр. 124-151
О реконструкции графов связности 2 с 2-вершинным множеством, делящим граф хотя бы на 3 части
Д. В. Карпов
Санкт-Петербургское отделение
Математического института им. В. А. Стеклова,
Российской академии наук,
наб. р. Фонтанки 27, 191023 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
{\em Колодой} графа $G$ называется набор графов $G-v$ для всех вершин $v$ графа $G$.
Обозначим колоду графа $G$ через ${\mathcal D}(G)$.
Пусть $G$ -- граф связности 2 и минимальной степени хотя бы 3, имеющий 2-вершинное разделяющее множество,
которое делит $G$ на 3 части.
В статье доказано, что такой граф можно восстановить по его колоде.
Доказательство содержит алгоритм восстановления графа.
Библ. -- 11 назв.
- Ключевые слова: восстановление графа, двусвязный граф
[graph reconstruction, 2-connected graphs]
Полный текст(.pdf)