Аннотация:
Для k-связного графа G определяется понятие блока и строится дерево блоков. Эта конструкция обобщает на случай k>1 известные конструкции для блоков связного графа. С помощью этих понятий дано описание множества вершин k-связного графа G, при удалении которых сохраняется k-связность. Исследован ряд вопросов, связанных с одновременным удалением нескольких вершин из k-связного графа без потери k-связности. Библ. – 4 назв.
Образец цитирования:
Д. В. Карпов, А. В. Пастор, “О структуре k-связного графа”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. V, Зап. научн. сем. ПОМИ, 266, ПОМИ, СПб., 2000, 76–106; J. Math. Sci. (N. Y.), 113:4 (2003), 584–597
\RBibitem{KarPas00}
\by Д.~В.~Карпов, А.~В.~Пастор
\paper О структуре $k$-связного графа
\inbook Теория представлений, динамические системы, комбинаторные и алгоритмические методы.~V
\serial Зап. научн. сем. ПОМИ
\yr 2000
\vol 266
\pages 76--106
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl1240}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1774649}
\zmath{https://zbmath.org/?q=an:1032.05075|1017.05064}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2003
\vol 113
\issue 4
\pages 584--597
\crossref{https://doi.org/10.1023/A:1021146226285}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl1240
https://www.mathnet.ru/rus/znsl/v266/p76
Эта публикация цитируется в следующих 31 статьяx:
D. V. Karpov, “On Semi-Reconstruction of Graphs of Connectivity 2”, J Math Sci, 275:2 (2023), 163
Н. Ю. Власова, “Каждый $3$-связный граф на не менее чем $13$ вершинах имеет стягиваемый $5$-вершинный подграф”, Комбинаторика и теория графов. XIII, Зап. научн. сем. ПОМИ, 518, ПОМИ, СПб., 2022, 5–93
Д. В. Карпов, “О реконструкции графов связности $2$ с $2$-вершинным множеством, делящим граф хотя бы на $3$ части”, Комбинаторика и теория графов. XIII, Зап. научн. сем. ПОМИ, 518, ПОМИ, СПб., 2022, 124–151
Karpov V D., “Large Contractible Subgraphs of a 3-Connected Graph”, Discuss. Math. Graph Theory, 41:1 (2021), 83–101
D. V. Karpov, “On semi-reconstruction of graphs of connectivity $2$”, Комбинаторика и теория графов. XII, Зап. научн. сем. ПОМИ, 497, ПОМИ, СПб., 2020, 80–99
Д. В. Карпов, “О правильных $3$-раскрасках ребер кубического графа”, Комбинаторика и теория графов. XI, Зап. научн. сем. ПОМИ, 488, ПОМИ, СПб., 2019, 31–48
А. В. Пастор, “О вершинах степени $6$ минимального и минимального по стягиванию $6$-связного графа”, Комбинаторика и теория графов. XI, Зап. научн. сем. ПОМИ, 488, ПОМИ, СПб., 2019, 143–167
Sandra Kiefer, Ilia Ponomarenko, Pascal Schweitzer, “The Weisfeiler–Leman Dimension of Planar Graphs Is at Most 3”, J. ACM, 66:6 (2019), 1
Н. Ю. Власова, “О стягиваемых 5-вершинных подграфах трёхсвязного графа”, Комбинаторика и теория графов. X, Зап. научн. сем. ПОМИ, 475, ПОМИ, СПб., 2018, 22–40
Д. В. Карпов, “О структуре трёхсвязного графа. 2”, Комбинаторика и теория графов. X, Зап. научн. сем. ПОМИ, 475, ПОМИ, СПб., 2018, 41–92
А. В. Пастор, “О критических трехсвязных графах ровно с двумя вершинами степени 3. Часть 2”, Комбинаторика и теория графов. X, Зап. научн. сем. ПОМИ, 475, ПОМИ, СПб., 2018, 137–173
Д. В. Карпов, “Разбиение двусвязного графа на три связных подграфа”, Комбинаторика и теория графов. IX, Зап. научн. сем. ПОМИ, 464, ПОМИ, СПб., 2017, 26–47; D. V. Karpov, “Decomposition of a $2$-connected graph into three connected subgraphs”, J. Math. Sci. (N. Y.), 236:5 (2019), 490–502
А. В. Пастор, “О критических трехсвязных графах ровно с двумя вершинами степени 3. Часть 1”, Комбинаторика и теория графов. IX, Зап. научн. сем. ПОМИ, 464, ПОМИ, СПб., 2017, 95–111; A. V. Pastor, “On critically $3$-connected graphs with exactly two vertices of degree 3. Part 1”, J. Math. Sci. (N. Y.), 236:5 (2019), 532–541
Sandra Kiefer, Ilia Ponomarenko, Pascal Schweitzer, 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2017, 1
А. В. Пастор, “О разбиении трехсвязного графа на циклически реберно-четырехсвязные компоненты”, Комбинаторика и теория графов. VIII, Зап. научн. сем. ПОМИ, 450, ПОМИ, СПб., 2016, 109–150; A. V. Pastor, “On a decomposition of a $3$-connected graph into cyclically $4$-edge-connected components”, J. Math. Sci. (N. Y.), 232:1 (2018), 61–83
Д. В. Карпов, “Удаление вершин из двусвязного графа с сохранением двусвязности”, Комбинаторика и теория графов. VII, Зап. научн. сем. ПОМИ, 427, ПОМИ, СПб., 2014, 66–73; D. V. Karpov, “Deleting vertices from a biconnected graph with preserving biconnectinity”, J. Math. Sci. (N. Y.), 212:6 (2016), 683–687
А. В. Пастор, “О структуре $C_3$-критических минимальных $6$-связных графов”, Комбинаторика и теория графов. VII, Зап. научн. сем. ПОМИ, 427, ПОМИ, СПб., 2014, 89–104; A. V. Pastor, “About vertices of degree $6$ of $C_3$-critical minimal $6$-connected graph”, J. Math. Sci. (N. Y.), 212:6 (2016), 698–707
Д. В. Карпов, “Дерево разбиения двусвязного графа”, Комбинаторика и теория графов. VI, Зап. научн. сем. ПОМИ, 417, ПОМИ, СПб., 2013, 86–105; D. V. Karpov, “The tree of decomposition of a biconnected graph”, J. Math. Sci. (N. Y.), 204:2 (2015), 232–243
Д. В. Карпов, “Минимальные двусвязные графы”, Комбинаторика и теория графов. VI, Зап. научн. сем. ПОМИ, 417, ПОМИ, СПб., 2013, 106–127; D. V. Karpov, “Minimal biconnected graphs”, J. Math. Sci. (N. Y.), 204:2 (2015), 244–257
А. Л. Глазман, “Обобщенные ромашки в $k$-связном графе. Часть 2”, Комбинаторика и теория графов. VI, Зап. научн. сем. ПОМИ, 417, ПОМИ, СПб., 2013, 11–85; A. L. Glazman, “Generalized flowers in $k$-connected graph. Part 2”, J. Math. Sci. (N. Y.), 204:2 (2015), 185–231
Цитирование в формате AMSBIB
Обратная связь: