Дата публикации: 2021

Дата публикации в реестре: 2022-10-06T22:21:27Z

Аннотация:

Рассматриваются двухцветные графы, то есть графы, вершины которых раскрашены в два цвета. Пусть G = (V, а, f) —цветной граф с определённой на множестве его вершин функцией раскраски f. Цветной граф G* называется вершинным 1-расширением цветного графа G, если граф G можно вложить с учётом цветов в каждый граф, получающийся из графа G* удалением любой его вершины вместе с инцидентными рёбрами. Вершинное 1-расширение G* графа G называется минимальным, если граф G* имеет на две вершины больше, чем граф G, а среди всех вершинных 1-расширений графа G с тем же числом вершин граф G* имеет минимальное число рёбер. Предлагается полное описание минимальных вершинных 1-расширений полных двухцветных графов. Пусть КП1,П2 —полный n-вершинный граф с П вершинами одного цвета и П2 вершинами другого цвета. Если в полном двуцветном графе ni = П2 = 1, то в минимальном вершинном 1-расширении такого графа будет одно дополнительное ребро. Если в полном двуцветном графе либо ni = 1, либо П2 = 1, то в минимальном вершинном 1-расширении такого графа будет 2п — 1 дополнительных рёбер. Во всех остальных случаях в минимальном вершинном 1-расширении полного двухцветного графа будет 2п дополнительных рёбер. Предлагаются схемы построения соответствующих минимальных вершинных 1-расширений. Bicolored graphs are considered, i.e., graphs whose vertices are colored in two colors. Let G = (V, a, f) be a colored graph with a coloring function f defined on the set of its vertices. A colored graph G* is called a vertex 1-extension of a colored graph G if the graph G can be embedded preserving the colors into each graph obtained from the graph G* by removing any of its vertices together with incident edges. A vertex 1-extension G* of a graph G is called minimal if the graph G* has two more vertices than the graph G, and among all vertex 1-extensions of the graph G with the same number of vertices the graph G* has the minimum number of edges. In this paper, we propose a full description of minimal vertex 1-extensions of complete bicolored graphs. Let Kni,n2 be a complete n-vertex graph with n1 vertices of one color and n2 vertices of a different color. If in a complete bicolored graph n1 = n2 = 1, then in the minimal vertex 1-extension of such a graph there is one additional edge. If in a complete bicolored graph either n1 = 1 or n2 = 1, then the minimal vertex 1-extension of such a graph has 2n — 1 additional edges. In all other cases, the minimal vertex 1-extension of a complete bicolored graph has 2n additional edges. The schemes for constructing the corresponding minimal vertex 1-extensions are proposed.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2021. № 14. С. 165-168