Записки научных семинаров ПОМИ
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Записки научных семинаров ПОМИ, 2013, том 417, страницы 86–105 (Mi znsl5706)  

Эта публикация цитируется в 14 научных статьях (всего в 14 статьях)

Дерево разбиения двусвязного графа

Д. В. Карповab

a С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, 191023 Санкт-Петербург, Россия
b Математико-механический факультет СПбГУ, Университетский пр., 28, 198504, Санкт-Петербург, Старый Петергоф
Список литературы:
Аннотация: Дерево разбиения $k$-связного графа набором $\mathfrak S$ из попарно независимых $k$-вершинных разделяющих множеств определяется следующим образом: вершины этого дерева – множества набора $\mathfrak S$ и части разбиения графа этим набором, каждое множество соединено с теми и только теми частями, которые его содержат. В работе доказывается, что построенный таким образом граф является деревом.
Частным случаем этой конструкции является дерево разбиения двусвязного графа. Это дерево разбиения двусвязного графа набором из его одиночных двухвершинных разделяющих множеств (то есть, независимых со всеми остальными двухвершинными разделяющими множествами).
Показано, что дерево разбиения двусвязного графа имеет много общего с классическим деревом блоков и точек сочленения связного графа. С помощью дерева разбиения двусвязного графа доказаны критерии планарности и оценки на хроматическое число этого графа.
Также с помощью дерева разбиения изучена структура критических двусвязных графов и показано, что любой такой граф имеет хотя бы четыре вершины степени 2. Библ. – 11 назв.
Ключевые слова: связность, двусвязный граф, разбиение, блоки.
Поступило: 31.10.2013
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2015, Volume 204, Issue 2, Pages 232–243
DOI: https://doi.org/10.1007/s10958-014-2198-z
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.173.1
Образец цитирования: Д. В. Карпов, “Дерево разбиения двусвязного графа”, Комбинаторика и теория графов. VI, Зап. научн. сем. ПОМИ, 417, ПОМИ, СПб., 2013, 86–105; J. Math. Sci. (N. Y.), 204:2 (2015), 232–243
Цитирование в формате AMSBIB
\RBibitem{Kar13}
\by Д.~В.~Карпов
\paper Дерево разбиения двусвязного графа
\inbook Комбинаторика и теория графов.~VI
\serial Зап. научн. сем. ПОМИ
\yr 2013
\vol 417
\pages 86--105
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl5706}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2015
\vol 204
\issue 2
\pages 232--243
\crossref{https://doi.org/10.1007/s10958-014-2198-z}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84925487835}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl5706
  • https://www.mathnet.ru/rus/znsl/v417/p86
  • Эта публикация цитируется в следующих 14 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:331
    PDF полного текста:90
    Список литературы:56
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024