Schemes for constructing minimal vertex 1-extensions of complete bicolored graphs

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 Kn₁,n₂ 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 n₁ = n₂ = 1, then in the minimal vertex 1-extension of such a graph there is one additional edge. If in a complete bicolored graph either n₁ = 1 or n₂ = 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.

Keywords

Authors

References