This article is cited in 3 papers

Applied Graph Theory

Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension

M. B. Abrosimov

Saratov State University named after N. G. Chernyshevsky, Sarartov, Russia

Abstract: A graph $G^*$ is $k$-vertex extension of graph $G$ if every graph obtained by removing any $k$ vertices from $G^*$ contains $G$. $k$-Vertex extension of graph $G$ with $n+k$ vertices is called minimal if, among all $k$-vertex extensions of graph $G$ with $n+k$ vertices, it has the minimum possible number of edges. The graphs whose minimal vertex 1-extensions have a specified number of additional edges are studied. A solution is given when the number of additional edges is equal to one, two or three.

Keywords: graph, minimal vertex extension, exact vertex extension, fault tolerance.

UDC: 519.17