This article is cited in 2 papers

Applied Graph Theory

Computational complexity of graph extensions

M. B. Abrosimov


Abstract: A graph $G^*$ is $k$-vertex (edge) extension of graph $G$ if every graph obtained by removing any $k$ vertexes (edges) from $G^*$ contains $G$. We prove NP-completeness of the problem: "Is graph $G^*$ a $k$-vertex (edge) extension of graph $G$?".

UDC: 519.17