|
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: | 205 | Full-text PDF : | 146 | References: | 50 |
|