minimal vertex extension

Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension

A graph G∗ is a k-vertex extension of a graph G if every graph obtained from G∗ by removing any k vertices contains G. k-vertex extension of a graph G with n+k vertices is called minimal if among all k-vertex extensions of G withn+k vertices it has the minimal possible number of arcs. We study directed graphs, whose minimal vertex 1-extensions have a specific number of additional arcs. A solution is given when the number of additional arcs equals one or two.