Characterization of graphs with a given number of additionaledges in a minimal 1-vertex extension | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 1(15).

A graph G* is k-vertex extension of graph G if every graph obtained by removing anyk vertices from G* contains G. k-Vertex extension of graph G with n + k vertices is calledminimal if, among all k-vertex extensions of graph G with n+k vertices, it has the minimumpossible number of edges. The graphs whose minimal vertex 1-extensions have a specifiednumber of additional edges are studied. A solution is given when the number of additionaledges is equal to one, two or three.