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

P. V. Razumovskii ; M. B. Abrosimov

Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 165-168

Résumé

Bicolored graphs are considered, i.e., graphs whose vertices are colored in two colors. Let $G = (V, \alpha, 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 $K_{n_1, n_2}$ be a complete $n$-vertex graph with $n_1$ vertices of one color and $n_2$ vertices of a different color. If in a complete bicolored graph $n_1 = n_2 = 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 = 1$ or $n_2 = 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.

Détail

Keywords: colored graph, complete graph, graph extension, minimal vertex graph extension, fault tolerance.