|
|
Prikladnaya Diskretnaya Matematika, 2011, Number 4(14), Pages 34–41
(Mi pdm341)
|
|
|
|
Applied Graph Theory
On minimal vertex 1-extensions of special type graph union
M. B. Abrosimov Saratov State University named after N. G. Chernyshevsky, Saratov, Russia
Abstract:
In 2001, it was conjectured that the minimal vertex 1-extension of a graph $G+G^*$, where $G^*$ is a minimal vertex 1-extension of graph $G$, is unique up to isomorphism and has the form $G^*+G^*$. We construct two counterexamples to this conjecture showing that, in general, it is wrong. Also, we show that the statement is true for many graphs.
Keywords:
graph, minimal vertex extension, exact vertex extension, fault tolerance.
Citation:
M. B. Abrosimov, “On minimal vertex 1-extensions of special type graph union”, Prikl. Diskr. Mat., 2011, no. 4(14), 34–41
Linking options:
https://www.mathnet.ru/eng/pdm341 https://www.mathnet.ru/eng/pdm/y2011/i4/p34
|
| Statistics & downloads: |
| Abstract page: | 426 | | Full-text PDF : | 216 | | References: | 141 |
|