RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2011 supplement № 4, Pages 81–82 (Mi pdm289)

Applied Graph Theory

On the uniqueness of exact vertex extensions

M. B. Abrosimov, A. A. Dolgov

Saratov State University named after N. G. Chernyshevsky, Saratov

Abstract: The paper discusses the uniqueness of the exact vertex extensions of graphs. This problem is closely related to reconstruction of graphs. For undirected graphs, the uniqueness has been proved earlier. For oriented graphs, full solution is not known. The obtained result means that if there is a digraph $G$ with the number of vertices greater than 2, which has two or more nonisomorphic 1-vertex exact extansions, the number of vertices of the digraph $G$ is not less than 13, and exact vertex 1-extensions are not reconstructible and do not belong to any known family of nonreconstructible digraphs.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2024