К вопросу о минимальных вершинных 1-расширениях с малым количеством дополнительных дуг

Граф G* = (V*, a*) называется минимальным вершинным k‑расширением  n‑вершинного графа G = (V, a), если выполняются следующие условия:

1. граф G* является вершинным k-расширением графа G, то есть граф G вкладывается в каждый граф, получающийся из G* удалением любых k вершин;
2. граф G* содержит n+k вершин, то есть |V*| = |V| + k;
3. a* имеет минимальную мощность среди всех графов, удовлетворяющих условиям 1) и 2).

Рассматриваются орграфы, которые имеют минимальные вершинные 1-расширения с малым числом дополнительных дуг.