|
Prikladnaya Diskretnaya Matematika, 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.
Citation:
M. B. Abrosimov, A. A. Dolgov, “On the uniqueness of exact vertex extensions”, Prikl. Diskr. Mat., 2011, supplement № 4, 81–82
Linking options:
https://www.mathnet.ru/eng/pdm289 https://www.mathnet.ru/eng/pdm/y2011/i13/p81
|
Statistics & downloads: |
Abstract page: | 135 | Full-text PDF : | 71 | References: | 51 |
|