|
Записки научных семинаров ПОМИ, 2017, том 464, страницы 26–47
(Mi znsl6520)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Разбиение двусвязного графа на три связных подграфа
Д. В. Карповab a С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023 С.-Петербург, Россия
b С.-Петербургский государственный университет, Университетский пр. 28, Старый Петергоф, 198504 Санкт-Петербург, Россия
Аннотация:
Пусть $G$ – двусвязный граф на $n$ вершинах такой, что каждое его двухэлементное разделяющее множество разбивает $G$ не более чем на 3 части, а $n_1+n_2 +n_3=n$. В работе доказано, что существует разбиение множества вершин графа $G$ на такие непересекающиеся подмножества $V_1$, $V_2$, $V_3$, что $|V_i|=n_i$ и индуцированный подграф $G(V_i)$ связен для каждого $i$. Библ. – 9 назв.
Ключевые слова:
двусвязный граф, разбиение, теорема Дьори–Ловаса.
Поступило: 22.11.2017
Образец цитирования:
Д. В. Карпов, “Разбиение двусвязного графа на три связных подграфа”, Комбинаторика и теория графов. IX, Зап. научн. сем. ПОМИ, 464, ПОМИ, СПб., 2017, 26–47; J. Math. Sci. (N. Y.), 236:5 (2019), 490–502
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6520 https://www.mathnet.ru/rus/znsl/v464/p26
|
Статистика просмотров: |
Страница аннотации: | 139 | PDF полного текста: | 46 | Список литературы: | 29 |
|