exact extension

On Directed Acyclic Exact Extensions

Authors: Abrosimov M. B.

Exact extensions of undirected graphs are well studied, but exact extensions of directed graphs are much less known.We prove that only directe dacyclicgraphor strongly connected graph can be an exact extension. Further more, only transitive tournament can be directed acyclic exact extension.

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

Authors: Abrosimov M. B.

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.