RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 519.173.1

Received: 27.10.2020

Language: English



© Steklov Math. Inst. of RAS, 2025