отказоустойчивая реализация

On Lower Bound of Edge Number of Minimal Edge 1-Extension of Starlike Tree

Authors: Abrosimov M. B.

For a given graph G with n nodes, we say that graph G∗ is its 1-edge extension if for each edge e of G∗ the subgraph G∗ −e contains graph G up to isomorphism. Graph G∗ is minimal 1-edge extension of graph G if G∗ has n nodes and there is no 1-edge extension with n nodes of graph G having fewer edges than G. A tree is called starlike if it has exactly one node of degree greater than two. We give a lower bound of edge number of minimal edge 1-extension of starlike tree and provide family on which this bound is achieved.

О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева

Authors: Abrosimov M. B.

Граф G* называется вершинным 1-расширением графа G, если граф G можно вложить в каждый граф, получающийся из графа G* удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение G* графа G называется минимальным, если граф G* имеет на одну вершину больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G* имеет минимальное число ребер. Дерево называется сверхстройным (звездоподобным), если только одна его вершина имеет степень больше двух.

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.