|
Zapiski Nauchnykh Seminarov POMI, 2020, Volume 497, Pages 80–99
(Mi znsl7028)
|
|
|
|
On semi-reconstruction of graphs of connectivity $2$
D. V. Karpovab a St. Petersburg Department of the Steklov Mathematical Institute
b St. Petersburg State University
Abstract:
Recall that the deck of a graph $G$ is the collection of subgraphs $G-v$ for all vertices $v$ of the graph $G$. We prove that at most two graphs of connectivity $2$ and minimal degree at least $3$ can have the same deck. Let $\mathcal{D}(G)$ be a deck of a $2$-connected graph $G$. We describe an algorithm which construct by the deck $\mathcal{D}(G)$ of a $2$-connected graph $G$ with minimal degree at least $3$ two graphs $G_1,G_2$ such that $G\in \{G_1,G_2\}$.
Key words and phrases:
graph reconstruction, $2$-connected graphs.
Received: 27.10.2020
Citation:
D. V. Karpov, “On semi-reconstruction of graphs of connectivity $2$”, Combinatorics and graph theory. Part XII, Zap. Nauchn. Sem. POMI, 497, POMI, St. Petersburg, 2020, 80–99
Linking options:
https://www.mathnet.ru/eng/znsl7028 https://www.mathnet.ru/eng/znsl/v497/p80
|
Statistics & downloads: |
Abstract page: | 112 | Full-text PDF : | 31 | References: | 21 |
|