Geodesic
Schemes for constructing minimal vertex $1$-extensions of complete bicolored graphs
Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 165-168 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: colored graph, complete graph, graph extension, minimal vertex graph extension, fault tolerance. 
@article{PDMA_2021_14_a38,
     author = {P. V. Razumovskii and M. B. Abrosimov},
     title = {Schemes for constructing minimal vertex $1$-extensions of complete bicolored graphs},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {165--168},
     year = {2021},
     number = {14},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2021_14_a38/}
}
TY  - JOUR
AU  - P. V. Razumovskii
AU  - M. B. Abrosimov
TI  - Schemes for constructing minimal vertex $1$-extensions of complete bicolored graphs
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2021
SP  - 165
EP  - 168
IS  - 14
UR  - http://geodesic.mathdoc.fr/item/PDMA_2021_14_a38/
LA  - ru
ID  - PDMA_2021_14_a38
ER  - 
%0 Journal Article
%A P. V. Razumovskii
%A M. B. Abrosimov
%T Schemes for constructing minimal vertex $1$-extensions of complete bicolored graphs
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2021
%P 165-168
%N 14
%U http://geodesic.mathdoc.fr/item/PDMA_2021_14_a38/
%G ru
%F PDMA_2021_14_a38
P. V. Razumovskii; M. B. Abrosimov. Schemes for constructing minimal vertex $1$-extensions of complete bicolored graphs. Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 165-168. http://geodesic.mathdoc.fr/item/PDMA_2021_14_a38/

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C-25:9 (1976), 875–884 | DOI | MR

[2] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997, 368 pp. | MR

[3] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp.

[4] Razumovskii P. V., Abrosimov M. B., “Postroenie tsvetnykh grafov bez proverki na izomorfizm”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 21:2 (2021), 267–277 | MR | Zbl

[5] Harary F., Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl