|
Zapiski Nauchnykh Seminarov POMI, 2017, Volume 464, Pages 26–47
(Mi znsl6520)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Decomposition of a $2$-connected graph into three connected subgraphs
D. V. Karpovab a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences, St. Petersburg, Russia
b St. Petersburg State University, St. Petersburg, Russia
Abstract:
Let $G$ be a $2$-connected graph on $n$ vertices such that any its $2$-vertex cutset splits $G$ into at most three parts and $n_1+n_2 +n_3=n$. We prove that there exists a decomposition of the vertex set of $G$ into three disjoint subsets $V_1$, $V_2$, $V_3$, such that $|V_i|=n_i$ and the induced subgraph $G(V_i)$ is connected for each $i$.
Key words and phrases:
$2$-connected graph, decomposition, Györi–Lovász theorem.
Received: 22.11.2017
Citation:
D. V. Karpov, “Decomposition of a $2$-connected graph into three connected subgraphs”, Combinatorics and graph theory. Part IX, Zap. Nauchn. Sem. POMI, 464, POMI, St. Petersburg, 2017, 26–47; J. Math. Sci. (N. Y.), 236:5 (2019), 490–502
Linking options:
https://www.mathnet.ru/eng/znsl6520 https://www.mathnet.ru/eng/znsl/v464/p26
|
Statistics & downloads: |
Abstract page: | 139 | Full-text PDF : | 46 | References: | 29 |
|