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

Prikl. Diskr. Mat., 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.

UDC: 519.17



© Steklov Math. Inst. of RAS, 2025